[G2] 백준 15559번 내 선물을 받아줘 C++ 깊이 우선 탐색

리뷰

 

https://www.acmicpc.net/problem/15559

오랜만에 재밌는 문제를 풀었다.

 

 

전역 변수

• n, m : 맵의 세로/가로 크기를 저장할 변수
• ans : 그룹의 개수를 저장할 변수
• lst : 이동할 방향의 인덱스를 저장할 2차원 배열
• g : 그룹 정보를 저장할 2차원 배열
• G : 그룹 번호를 저장할 변수
• B :  재귀를 빠져나올 때의 그룹 번호를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. dfs

void dfs(int x, int y)

 

깊이 우선 탐색을 통해 그루핑을 진행하기 위한 함수

1. 매개 변수로 탐색을 진행할 위치의 좌표 x, y를 전달 받는다.
2. 첫 번째 기저 조건으로 현재 위치의 그룹이 G와 동일할 경우 리턴해 준다.
3. 두 번째로 현재 위치의 그룹이 지정 되었으며 G보다 작을 경우 B를 해당 그룹번호로 변경 및 ans감소 후 리턴한다.
4. 현재 lst배열에 저장된 인덱스를 통해 이동할 위치를 변수 nx, ny에 저장해 준다.
5. 현재 위치의 그룹을 G로 변경해 주고, dfs함수에 nx, ny를 매개변수로 전달해 재귀를 진행해 준다.
6. 재귀를 빠져나오며 현재 위치의 그룹을 B로 변경해 준다.

 

문제풀이

1. n, m에 값을 입력 받고, n * m크기의 맵 정보를 입력 받는다.
2. 입력 받은 문자가 N, W, E, S일 경우 각각 lst에 0, 1, 2, 3으로 저장해 준다.
3. n * m크기의 맵을 순회하며 아직 그룹이 매핑되지 않은 경우 G를 전위증가 시키고 B에 값을 복사해 준다.
4. ans를 증가시킨 후 현재 위치를 dfs함수의 매개 변수로 전달하여 그루핑을 진행해 준다.
5. 맵을 모두 순회하였으면 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 결국 맵을 돌다보면 사이클이 생긴다, 사이클을 발생했을 때 해당 그룹을 하나의 그룹으로 만들어 주면 된다.
• 사이클의 시작점은 어디인지 모르는 상태이기 때문에 이미 이전에 그루핑된 그룹과 연결된 경우 현재 탐색중이던 그룹을 해당 그룹으로 변경해 주면 된다.
• 이를 플러드필을 통해 구현할까 했지만 그냥 재귀를 빠져나올 때 갱신을 해주면 된다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n, m, ans;
int lst[1000][1000];
int g[1000][1000];
int G, B;
int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };

void dfs(int x, int y) {
	if (g[x][y] == G) return;
	if (g[x][y] && g[x][y] < G) {
		B = g[x][y];
		ans--;
		return;
	}

	int nx = x + dx[lst[x][y]], ny = y + dy[lst[x][y]];
	g[x][y] = G;
	dfs(nx, ny);
	g[x][y] = B;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		string s; cin >> s;
		for (int j = 0; j < m; ++j) {
			if (s[j] == 'N') lst[i][j] = 0;
			else if (s[j] == 'W') lst[i][j] = 1;
			else if (s[j] == 'E') lst[i][j] = 2;
			else lst[i][j] = 3;
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (!g[i][j]) {
				B = ++G;
				ans++;
				dfs(i, j);
			}
		}
	}

	//for (int i = 0; i < n; ++i) {
	//	for (int j = 0; j < m; ++j) {
	//		cout << g[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	cout << ans;
}