[백준/C++] 14868번: 문명

뭔지 모르게 서핑하다가 union-find문제를 발견하였는데 아직 한번도 풀어본 적이 없어서 경험삼아 한번 풀어보았다. 생각보다 개념은 어렵지 않다. 두 개의 다른 집단이 인접하였고 또 서로 index가 다르다면 합치면 된다. 종료조건은 집단이 하나만 남았을 때로 하면 된다. (www.youtube.com/watch?v=_N0hk13QM6w)

 

#include<iostream>
#include<queue>
using namespace std;
int N, K, civ[2002][2002], year;

queue<pair<int, int>> q, qq;

int p[1000002], Rank[1000002];
int root(int x) {
	if (x == p[x]) return x; // x라는 값이 해당 부모의 값과 동일하다면 x를 return
	return root(p[x]); // 다르면 부모를 찾는다. 재귀적으로
}

bool unions(int x, int y) {
	x = root(x);
	y = root(y);

	if (x == y) return true;
	else {
		if (Rank[x] > Rank[y]) p[y] = x; //y가 x의 밑으로 들어가니까
		else if (Rank[x] < Rank[y]) p[x] = y;
		else { //rank 2개가 같다는 거니까 x밑으로 넣어주자(x밑으로 넣어줘도 되고 y밑으로 넣어줘도 되고)
			Rank[x]++;
			p[y] = x;
		}

		return false;
	}
}

int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };
void bfs() {
	while (1) {

		while (!q.empty()) { //합칠 수 있는 문명을 다 합쳐준다.
			int cx = q.front().first;
			int cy = q.front().second;
			qq.push(q.front());
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
				if (civ[nx][ny] != 0 && civ[nx][ny] != civ[cx][cy]) {
					if (!unions(civ[nx][ny], civ[cx][cy])) {
						K--;
					}
				}

			}

		}


		if (K == 1) {
			cout << year;
			return;
		}

		while (!qq.empty()) { // 문명을 전파시킨다.
			int cx = qq.front().first;
			int cy = qq.front().second;
			qq.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx <= 0 || nx > N || ny <= 0 || ny > N) continue;
				if (civ[nx][ny] == 0) {
					civ[nx][ny] = civ[cx][cy];
					q.push({ nx,ny });
				}
				else if (civ[nx][ny] != civ[cx][cy]) {
					if (!unions(civ[nx][ny], civ[cx][cy])) {
						K--;
					}
				}
				

			}

		}

		year++;


	}
}

int main() {

	cin >> N >> K;

	for (int i = 1; i <= K; i++) {
		int x, y;
		cin >> x >> y;
		p[i] = i;
		civ[x][y] = i;
		q.push({ x,y });

	}

	bfs();

	return 0;
}