[백준] 플래티넘5 : (3197) 백조의 호수

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

 

정석은 분리 집합(Disjoint Set)을 활용해서 푸는 것 같다.

나는 직접적으로 분리 집합을 활용하여 풀지는 않았지만, 이론을 비슷하게 사용했기 때문에 풀린 것 같다.

 

먼저, 분리 집합과 비슷하게 각 물 좌표마다 물 번호를 매겼다.

이는 서로 이어져있을 시, 같은 번호를 공유한다.

 

물을 모두 순회하며, 닿는 빙하들에 자신의 물 번호를 매기고, 큐에 담는다.

이러면, 매 날짜마다 해동되는 새 물만이 큐에 담기게 된다. (0번째 날 제외)

 

물 큐를 순회하며, 각자 BFS를 실행해서 물 번호를 갱신한다.

빙하가 녹아 두 물이 합쳐질 수 있게 되면, 여기서 물 번호가 합쳐질 것이다.

 

두 백조의 물 번호를 비교하여 같으면 종료한다.

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

int dy[]{ -1,0, 1, 0 };
int dx[]{ 0, 1, 0, -1 };
int R, C;

void Func(vector<vector<pair<bool, int>>>& Map, queue<pair<int, int>> Water)
{
	// 임의의 물 번호 (초기에 해당 물이 번호가 없는 경우를 대비)
	int Index = 0;
	vector<vector<bool>> Visit(R, vector<bool>(C, false));

	while (!Water.empty())
	{
		int y = Water.front().first, x = Water.front().second;
		Water.pop();

		if (Visit[y][x]) continue;

		// 해당 물 기준으로 BFS를 돌려, 갈 수 있는 모든 물에 번호를 통일시킴 & 방문 처리
		queue<pair<int, int>> q;
		q.push({ y, x });
		Visit[y][x] = true;

		while (!q.empty())
		{
			int yy = q.front().first, xx = q.front().second;
			q.pop();

			if (Map[yy][xx].second == -1) Map[yy][xx].second = Index++;

			for (int i = 0; i < 4; ++i)
			{
				int ny = yy + dy[i], nx = xx + dx[i];

				if (ny < 0 || ny >= R || nx < 0 || nx >= C || Map[y][x].second == Map[ny][nx].second) continue;
				if (Map[ny][nx].first) continue;

				Map[ny][nx].second = Map[y][x].second;
				q.push({ ny, nx });
			}
		}
	}
}

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

	cin >> R >> C;

	// 지난 날짜
	int Day = 0;

	// 백조의 위치 (임의의 좌표로 초기화)
	pair<int, int> S1{ -1, -1 }, S2{ -2, -2 };

	// 맵 정보, { 물/빙하 여부, 물 번호 ]
	vector<vector<pair<bool, int>>> Map(R, vector<pair<bool, int>>(C, { false, -1 }));

	// 빙하를 녹이는 물의 위치 큐
	queue<pair<int, int>> Water;

	for (int i = 0; i < R; ++i)
	{
		for (int j = 0; j < C; ++j)
		{
			char k = 0;
			cin >> k;
			switch (k)
			{
			case '.': Water.push({ i, j });
				break;
			case 'X': Map[i][j].first = 1;
				break;
			case 'L': Water.push({ i, j });
				S1.first == -1 ? S1 = { i, j } : S2 = { i, j };
				break;
			default: break;
			}
		}
	}

	while (true)
	{
		// 물 번호 매기기
		Func(Map, Water);

		// 백조1이 있는 물과 백조2가 있는 물의 번호가 같으면 중단
		if (Map[S1.first][S1.second].second == Map[S2.first][S2.second].second) break;

		// 빙하를 녹이는 물의 위치를 순회하며, 빙하를 녹임
		int Size = Water.size();
		for (int i = 0; i < Size; ++i)
		{
			int y = Water.front().first, x = Water.front().second;
			Water.pop();

			for (int i = 0; i < 4; ++i)
			{
				int ny = y + dy[i], nx = x + dx[i];

				// 빙하만 조사
				if (ny < 0 || ny >= R || nx < 0 || nx >= C || !Map[ny][nx].first) continue;

				Map[ny][nx].first = false;
				Map[ny][nx].second = Map[y][x].second;
				Water.push({ ny, nx });
			}
		}
		Day++;
	}

	cout << Day << "\n";
}