[BOJ] 14868 : 문명 - travelbeeee

문제 : https://www.acmicpc.net/problem/14868

---

[ 알고리즘풀이 ]

 BFS 탐색과 Union-Find 로 문제를 해결할 수 있습니다.

1) 먼저, 입력 받은 문명지들마다 Numbering 을 해줍니다.

2) 입력 받은 문명지들을 순회하며 주변에 다른 문명이 있다면 Union-Find 를 통해 문명을 결합합니다. 처음에는 K개의 문명이 있지만, 문명을 결합할 때마다 문명의 개수를 K-- 를 통해 낮춰줍니다.

3) 문명의 개수가 1인지 체크하고, 1이라면 종료합니다.

4) 1이 아니라면, 문명지들을 다시 주변으로 전파해줍니다. 그 후, 2번부터 다시 반복합니다.

 

// 문제의 핵심은 문명을 먼저 결합하고, 그 뒤에 전파해야됩니다! 

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

int N, K, x, y, root[4000000];
int map[2000][2000];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };

queue<pair<int, int>> q1, q2;

int find(int num) {
	if (root[num] == num)
		return num;
	return root[num] = find(root[num]);
}

bool merge(int num1, int num2) {
	int pNum1 = find(num1), pNum2 = find(num2);
	if (pNum1 == pNum2)
		return false;
	root[pNum1] = pNum2;
	return true;
}

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

	cin >> N >> K;

	for (int i = 0; i < N * N; i++)
		root[i] = i;

	for (int i = 1; i <= K; i++) {
		cin >> x >> y;
		x--, y--;
		map[x][y] = i;
		q1.push({ x, y });
	}

	int ans = 0, curCivil = K;
	while (1) {
		// 문명 결합
		int qSize = q1.size();
		for (int i = 0; i < qSize; i++) {
			pair<int, int> cur = q1.front();
			q1.pop();
			q2.push(cur);
			int x = cur.first, y = cur.second;

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j], ny = y + dy[j];
				if (!(0 <= nx && nx < N && 0 <= ny && ny < N))
					continue;
				if (map[nx][ny] != 0) {
					bool check = merge(map[x][y], map[nx][ny]);
					if (check)
						curCivil--;
				}
			}
		}
		if (curCivil == 1)
			break;
		// 문명전파
		qSize = q2.size();
		for (int i = 0; i < qSize; i++) {
			pair<int, int> cur = q2.front();
			q2.pop();

			int x = cur.first, y = cur.second;
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j], ny = y + dy[j];
				if (!(0 <= nx && nx < N && 0 <= ny && ny < N))
					continue;
				if (map[nx][ny] == 0) {
					q1.push({ nx, ny });
					map[nx][ny] = map[x][y];
				}
			}
		}
		ans++;
	}
	cout << ans << '\n';
	return 0;
}

---