백준 16724번 | 피리 부는 사나이 (C++ 풀이)

  문제  

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

16724번: 피리 부는 사나이

---

  풀이  

• 사용 알고리즘 : Union-Find or DFS

문제를 잘 해석해 보면, SAFE-ZONE의 최소 개수는 결국 그래프의 컴포넌트 개수와 같다는 점을 이용해서 풀 수 있습니다. 단, 사이클이 존재하는 단방향 그래프이기 때문에 추가적인 생각이 필요했던 문제였습니다. 컴포넌트의 개수를 구하는 풀이는 Union-Find 나 DFS 정도가 있을 것 같고, 이 글에서는 두 가지 풀이 모두 다뤄보겠습니다.

 

첫 번째 풀이: DFS

컴포넌트의 개수를 잘 구해주기만 하면 되는데, 이때 방문 처리를 어떻게 할 것인지를 생각해봐야 합니다. 단순하게 한번 방문한 곳은 고려 대상에서 아예 제외하는 방향으로 설계하면 이 문제를 풀 수 없는데요, 그 이유는 단방향 그래프이면서 필연적으로 사이클이 존재하기 때문입니다. 이해가 잘 안 가실 수도 있으니 아래 그림을 봐보죠.

이런 그래프가 있습니다. 그리고 제가 동그라미 해놓은 곳은 처음에 탐색을 시작할 위치들입니다. 먼저 파란 동그라미에서 처음 탐색을 시작했다고 가정하고 컴포넌트를 구해보면,

이런 식으로 구해질 거고, 실제로 맞는 답을 구할 수 있습니다.

그렇다면 빨간 동그라미에서 처음 탐색을 시작한다면 어떨까요?

한번 방문한 곳은 고려 대상에서 제외했으니, 컴포넌트의 개수가 2개로 구해질 겁니다. 이렇게 되면 틀린 답을 구하게 되겠죠.

즉, 이런 식으로는 처음 탐색을 시작해서 구한 컴포넌트가 최소의 컴포넌트임을 보장할 수 없습니다.

 

그렇다면 한번 방문했다고 해서 무조건적인 고려 제외는 답이 아닌 듯하고, 가장 큰 문제는 그래프의 사이클이니 이와 관련해서 방문 처리를 두 가지 경우로 나눠서 생각해 보면 어떨까요?

 

1. 첫 사이클이 만들어질 때

이 경우는 큰 문제가 없습니다. 일단 사이클이 처음 만들어졌다는 것은 새로운 컴포넌트가 발견됐다는 점이겠죠. 이때는 답에서 +1 해주면 됩니다. 

 

2. 이미 만들어진 사이클에 진입할 때

이 경우가 위 그림에서 문제가 됐던 부분이죠. 만약 "이미 만들어진 사이클"이라는 것을 알 수만 있다면, 기존의 컴포넌트에 들어가는 것이니 이때는 컴포넌트 개수를 올리지 않고 그냥 넘겨주기만 하면 됩니다.

그럼 이제 "만들어지고 있는 사이클"과 "이미 만들어진 사이클"을 구분해주기만 하면 되는데, 이는 방문하고 있는 상태 값을 1, 이미 방문을 완료한 상태 값을 2로 설정하여 구분할 수 있습니다. 한 턴마다 그래프의 사이클이 반드시 완성되므로, DFS 함수 진입 시점에 1, 종료 시점에 2를 주어서 마치 백트래킹의 느낌으로 구현할 수 있습니다.

 

 

두 번째 풀이: Union-Find

유니온 파인드 풀이의 논리 흐름은 꽤 간단합니다. 연결된 노드들을 Union 시켜주고, 같은 루트를 가진다면 같은 컴포넌트에 속해있음을 이용해서 서로 다른 컴포넌트의 개수를 세어주면 되겠죠.

 

또한, 그래프의 모든 노드들에 대한 Union 연산을 마쳤다면, 전체적인 노드들에 대해서 경로 압축 최적화를 시켜줘서 자신이 속한 컴포넌트의 최상위 루트 노드를 가리키게 만들어줘야 합니다. 그렇지 않으면 같은 컴포넌트에 속해있어도 서로 다른 루트를 가리킬 수 있습니다.

 

---

  코드  

DFS

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

int visited[1001][1001];
int mmap[1001][1001];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int ans = 0;

void go(int x, int y) {
	visited[x][y] = 1;
	int dir = mmap[x][y];
	int nx = x + dx[dir];
	int ny = y + dy[dir];
	if (visited[nx][ny] == 0) go(nx, ny);
	if (visited[nx][ny] == 1) ans++; // 사이클 발견
	visited[x][y] = 2;
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			if (s[j] == 'U') mmap[i][j] = 0;
			else if (s[j] == 'D') mmap[i][j] = 1;
			else if (s[j] == 'L') mmap[i][j] = 2;
			else if (s[j] == 'R') mmap[i][j] = 3;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visited[i][j] != 0) continue;
			go(i, j);
		}
	}
	cout << ans;
	return 0;
}

Union-Find

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

int p[1000001];
int mmap[1001][1001];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int find(int x) {
	if (p[x] == x) return x;
	return p[x] = find(p[x]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[b] = a;
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			if (s[j] == 'U') mmap[i][j] = 0;
			else if (s[j] == 'D') mmap[i][j] = 1;
			else if (s[j] == 'L') mmap[i][j] = 2;
			else if (s[j] == 'R') mmap[i][j] = 3;
		}
	}
	for (int i = 0; i < n * m; i++) p[i] = i;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int curNode = m * i + j;
			int dir = mmap[i][j];
			int nx = i + dx[dir];
			int ny = j + dy[dir];
			int nextNode = m * nx + ny;
			merge(nextNode, curNode);
		}
	}
	for (int i = 0; i < n * m; i++) find(i);
	set<int> s;
	for (int i = 0; i < n * m; i++) s.insert(p[i]);
	cout << s.size();
	return 0;
}