[백준] #16724번 피리 부는 사나이 (C++)

문제

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

지도에 방향이 주어졌을 때, 지도 어느 구역에 있더라도 SAFE ZONE에 갈 수 있게 하는 SAFE ZONE의 최소 개수를 구하는 문제입니다.

문제 풀이

예제에 있는 지도를 그려보면 아래와 같습니다.

각 칸마다 지나갈 수 있는 경로를 탐색하며 하나의 '집합'으로 묶어주면 아래와 같습니다. 총 2개의 집합이 나오며, 경로 각각 1개(총 2개)의 SAFE ZONE만 설치해주면 어디에서든 SAFE ZONE에 도달할 수 있다는 사실을 알 수 있습니다.

또 다른 경우를 살펴보겠습니다. 각 칸에서 갈 수 있는 경로를 집합으로 묶으면, 3개의 집합이 나오게 됩니다. 즉, 3개의 SAFE ZONE만 설치해주면 됩니다.

즉, 경로 집합의 총개수가 SAFE ZONE의 최솟값임을 알 수 있습니다.

소스코드

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1001
#define p pair<int, int>

int n, m, result;
char mapp[MAXN][MAXN];
p parent[MAXN][MAXN]; // (1)
map<char, p> dir;

p find(int y, int x) {
	int py = parent[y][x].first, px = parent[y][x].second;

	if (py == y && px == x) {
		p tmp;
		tmp.first = y; tmp.second = x;
		return tmp;
	}
	else {
		return parent[y][x] = find(py, px);
	}
}

bool check_range(int y, int x) {
	if (y > 0 && x > 0 && y <= n && x <= m) return true;
	return false;
}

void dfs(int y, int x) {
	if (!check_range(y, x)) {
		parent[y][x] = { y, x };
		result++;
		return;
	}

	int ny = y + dir[mapp[y][x]].first, nx = x + dir[mapp[y][x]].second;
	
	if (parent[ny][nx].first == 0 && parent[ny][nx].second == 0) {
		parent[ny][nx] = { y, x }; // (3)
		dfs(ny, nx);
	}
	else if (find(y, x) == find(ny, nx)) {
		result++; // (4)
		return; 
	}
	else if (find(y, x) != find(ny, nx)) {
		return; // (5)
	}
}

int main() {
	cin >> n >> m;

	dir.insert({ 'R', {0, 1} });
	dir.insert({ 'L', {0, -1} });
	dir.insert({ 'U', {-1, 0} });
	dir.insert({ 'D', {1, 0} });

	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= m; k++) {
			cin >> mapp[i][k];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= m; k++) {
			if (parent[i][k].first == 0 && parent[i][k].second == 0) {
				parent[i][k] = { i, k }; // (2)
				dfs(i, k);
			}
		}
	}

	cout << result;
}

프로세스

1. 각 칸의 좌표의 부모 좌표를 (0, 0)으로 초기화 해줍니다. 이는 곧 현재 좌표가 방문하지 않음을 뜻합니다.
   
   

2. 지도를 순차 탐색을 하며 만약 현재 좌표의 부모 좌표가 (0, 0)이라면 DFS 탐색을 수행합니다. 이때, DFS를 수행하는 시작 좌표를 앞으로 탐색할 경로의 루트(최상단) 좌표로 설정합니다.
   
   

3. 만약 DFS 탐색 과정에서 부모 좌표가 (0, 0)이라면(방문 X) 부모 좌표를 갱신해주고, 다시 DFS 연산을 수행합니다.
   
   

4. 만약 탐색 과정에서 (0, 0)이 아니고(이미 방문), 부모 좌표가 같다면 이는 하나의 집합이 완성(싸이클 발생)된 것이므로 탐색을 종료하고 결과를 +1 해줍니다.
   
   

5. 만약 탐색 과정에서 (0, 0)이 아니고(이미 방문), 부모 좌표가 다르다면 이미 집합이 형성된 경로이므로 현재 경로를 병합해줍니다. (탐색 종료)