[DFS/BFS] 15559번 내 선물을 받아줘

• 문제

백준 15559번 내 선물을 받아줘

www.acmicpc.net/problem/15559

15559번: 내 선물을 받아줘

 

• 문제풀이

 DFS 또는 BFS 둘 중 어떤걸로 풀어도 상관없을 것 같고, DFS를 이용하여 문제를 풀었다.

 

 다행히 문제 예제 입력에서 힌트를 얻어 문제에서 요구하는 바를 깨달을 수 있었다.

 

 문제 예제에서 

SWWW
SEWN
EEEN

와 같은 입력이 주어진 것을 보고

 

1번 그림

 

 

 다음과 같은 노드와 엣지로 이루어진 그래프를 그릴 수 있었다.

 

 따라서 세로길이 N과 가로길이 M의 곱셈인 N * M은 총 노드의 개수가 된다.

 

 또한 위 그림을 보면 2개의 그래프가 존재하기에 욱제가 구사과를 위해 놓아야 할 선물의 최소 개수 또한 2개가 된다.

 

 따라서 DFS를 실행하고 난 뒤에 방문하지 않은 정점에서부터 다시 DFS를 실행. 이 과정을 모든 정점을 방문할 때 까지 반복하면 해당 반복횟수가 문제의 정답이 된다. 

 

+

하지만 추가로 주의해야 할 점이 있다.

 

2번 그림

 6번 노드가 7번 노드와 연결되었던 1번 그림과 달리 10번 노드와 연결된다면 모든 정점이 연결된 완전 그래프이기 때문에 해당 예시의 정답은 1이 된다. 하지만 현재 방향이 있는 그래프 상태에서 DFS(START = 1)를 실행하게 되면 첫 실행에서 노드 6과 노드7은 방문하지 않기에 오답이 나오게 된다.

 

 따라서 엣지는 무방향 그래프로 설정되어야만 하고 입력을 받을 때 에도 양방향이 되게끔 인접리스트를 만들어줘야 한다.

 

• 코드 구현

#include <iostream>
#include <vector>
#include <map>
#include<stack>

using namespace std;

#define MAX 1000001



vector<int> graph[MAX];
vector<bool> visited;



void dfs(int start) {
	stack<int> s;

	s.push(start);
	visited[start] = true;

	while (!s.empty()) {
		int curr = s.top();
		//cout << "curr" << curr << "  ";
		s.pop();

		for (int i = 0; i < graph[curr].size(); ++i) {
			int next = graph[curr][i];
			//cout << "next" << next << endl;
			if (visited[next]) continue;
			s.push(next);
			visited[next] = true;
		}
	}
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	int numOfNode;
	int answer=0;

	char word;

	
	cin >> N >> M;

	//가로 길이 N이고, 세로 길이가 M이니까
	//만약 위나 아래로 내려가면 +-M씩
	//옆으로 가면 +-1씩
	numOfNode = N * M;
	
	visited = vector<bool>(numOfNode + 1,0);
	
	
	for (int i = 1; i <= numOfNode; ++i) {
	
		cin >> word;
		switch (word) {
			//아래로 간다.
		case 'S':
			graph[i].push_back(i + M);
			graph[i + M].push_back(i);
			break;
			//위로 간다.
		case 'N':
			graph[i].push_back(i - M);
			graph[i - M].push_back(i);
			break;
			//오른쪽으로 간다. +1
		case 'E':
			graph[i].push_back(i + 1);
			graph[i + 1].push_back(i);
			break;
		case 'W':
			graph[i].push_back(i - 1);
			graph[i - 1].push_back(i);
			break;
		}
	}


	for(int i=1; i<=numOfNode; ++i) {
		if (visited[i]) continue;
		dfs(i);
		answer++;
	}
	
	cout << answer;
}