백준 3197번 : 백조의 호수 BFS Union&Find C++

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

3197번: 백조의 호수

#include <bits/stdc++.h>
using namespace std;

int r, c;
char arr[1501][1501];
int num[1501][1501];
int unf[1501 * 1501];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int Find(int x) {
	if (unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

void merge(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	unf[x] = y;
}

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

	memset(unf, -1, sizeof(unf));
	vector<pair<int, int> > swan;
	queue<pair<int, int> > water;

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		string s;
		cin >> s;

		for (int j = 0; j < c; j++) {
			arr[i][j] = s[j];
			if (arr[i][j] == 'L') {
				swan.push_back({ i,j });
				arr[i][j] = '.';
			}
			else if (arr[i][j] == 'X') {
				num[i][j] = -1;
				continue;
			}
			water.push({ i,j });
		}
	}

	//독립적으로 물이 있는 영역을 구해준다.
	int cnt = 1;
	queue<pair<int, int> > Q;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (num[i][j] == 0) {
				num[i][j] = cnt;
				Q.push({ i,j });
				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];
						if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
						if (num[nx][ny] == 0) {
							num[nx][ny] = num[x][y];
							Q.push({ nx,ny });
						}
					}
				}
				cnt++;
			}
		}
	}


	int t = 0;

	if (Find(num[swan[0].first][swan[0].second]) == Find(num[swan[1].first][swan[1].second])) {
		cout << t << '\n';
		return 0;
	}


	while (!water.empty()) {
		int q = water.size();

		//물로 빙하를 물로 만든다.
		for (int j = 0; j < q; j++) {
			int x = water.front().first;
			int y = water.front().second;
			water.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if (arr[nx][ny] == 'X') {
					arr[nx][ny] = '.';
					num[nx][ny] = num[x][y];
					water.push({ nx,ny });
				}
				else {
					merge(num[x][y], num[nx][ny]);
				}
			}
		}

		//현재 얼음이 물이 되어서 합쳐져야 될 영역이 있다면 합친다
		q = water.size();
		for (int j = 0; j < q; j++) {
			int x = water.front().first;
			int y = water.front().second;
			water.pop();

			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				if (arr[nx][ny] == '.') {
					merge(num[x][y], num[nx][ny]);
				}
			}
			water.push({ x,y });
		}

		t++;
		if (Find(num[swan[0].first][swan[0].second]) == Find(num[swan[1].first][swan[1].second])) {
			cout << t << '\n';
			return 0;
		}
	}




	return 0;
}

백준 3197번 백조의 호수