백준 3197: 백조의 호수

문제 요약

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• BFS
• 분리 집합

문제 풀이

백조와 인접한 물을 하나의 집합으로 처리하고, 얼음을 녹여가며 두 백조가 같은 집합에 속해있는지 BFS로 확인하면 된다. 입력을 받으면서 'L'이 입력 되었을 때, 각각 Lpos1과 Lpos2에 저장해줌으로써 백조의 위치를 기억해주었다. 그리고 nearby()를 통해 해당 칸을 기준으로 집합을 만드는데, 주변에 물('.')이 있으며, 해당 칸이 자신과 다른 집합일 때 두 집합을 병합해주며 nearby()를 재귀호출해 주었다. 여기서 만일 다음칸이 얼음('X')이라면, 큐에 삽입하여 얼음을 녹일 준비를 했다. 또한, 같은 얼음이 큐에 두 번 삽입되지 않도록 visited를 통해 가려내주었다. 이 nearby()는 DFS로하여, 인접한 물의 칸을 모두 집합으로 처리한다.

입력을 전부 받은 뒤에, 이번에는 백조가 속하지 않은 호수에 대해서도 같은 nearby()를 해준다. 인접한 물을 하나의 집합으로 처리하고, 해당 집합에 인접한 얼음을 큐에 넣어주는 작업이다. 이것으로 일차적인 얼음을 녹일 준비는 끝났다.

이후 얼음을 녹여가며 BFS를 하는데, 현재 얼음인 칸을 물('.')로 바꾸고, 주변 인접칸을 확인한다. 주변에 이미 물이 있을 경우 해당 집합에 병합시키고, 얼음이 있을 경우 다음에 녹여야 할 얼음이므로 큐에 삽입한다. 물론 visited를 true로 바꿔서 중복 삽입되지 않도록 한다. 또, 얼음을 녹일 때에는 위의 nearby()와 다르게 다음 칸이 백조('L')인 경우도 집합을 병합해주어야 하므로 해당 조건문을 추가해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int p[2250001], r, c;
bool visited[1500][1500];
string map[1500];
queue<int> q;

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

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

void nearbyWater(int t) {
	int y = t / c;
	int x = t % c;
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		int nt = ny * c + nx;
		if (nx >= 0 && nx < c && ny >= 0 && ny < r) {
			if (find(nt) != find(t) && map[ny][nx] == '.') {
				merge(t, nt);
				nearbyWater(nt);
			}
			else if (map[ny][nx] == 'X' && !visited[ny][nx]) {
				visited[ny][nx] = true;
				q.push(nt);
			}
		}
	}
}

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

	int level = 0, qsize, Lpos1 = -1, Lpos2, nx, ny, nt;
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		cin >> map[i];
		for (int j = 0; j < c; j++) {
			p[i * c + j] = i * c + j;
			if (map[i][j] == 'L') {
				if (Lpos1 == -1)
					Lpos1 = i * c + j;
				else
					Lpos2 = i * c + j;
			}
		}
	}
	nearbyWater(Lpos1);
	nearbyWater(Lpos2);
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] == '.')
				nearbyWater(i * c + j);
		}
	}
	while (!q.empty()) {
		if (find(Lpos1) == find(Lpos2)) break;
		level++;
		qsize = q.size();
		while (qsize--) {
			auto& t = q.front();
			int cx = t % c, cy = t / c;
			map[cy][cx] = '.';
			for (int i = 0; i < 4; i++) {
				nx = cx + dir[i][0];
				ny = cy + dir[i][1];
				nt = ny * c + nx;
				if (nx >= 0 && nx < c && ny >= 0 && ny < r) {
					if (map[ny][nx] == '.' || map[ny][nx] == 'L')
						merge(t, nt);
					else if (!visited[ny][nx]) {
						visited[ny][nx] = true;
						q.push(nt);
					}
				}
			}
			q.pop();
		}
	}
	cout << level;
}