백준14868 문명

작성일 | In

문제 링크

  • http://icpc.me/14868

문제 출처

  • 2017 KOI 전국 본선 고등부2

사용 알고리즘

  • BFS
  • Union Find

시간복잡도

  • O(n^2)

풀이

인접한 지역에 문명을 전파한다는 점에서 BFS가, 문명이 결합된다는 접에서 Union Find를 떠올리시면 됩니다.

BFS함수를 두 가지 만들 것입니다.
하나는 문명을 결합하는 bfs_union, 또 다른 하나는 문명을 전파하는 bfs_propagation를 만들어서 매 해마다 돌릴 것입니다.
bfs_union은 현재 지역에서 인접한 지역이 문명 지역이고, 나와 다른 문명이라면 문명을 결합해주는 아주 간단한 함수입니다.
bfs_propagation은 두 가지 경우를 처리해주어야 합니다. 만약 현재 지역이 문명 지역이고, 인접한 지역이 미개 지역이라면 현재 문명을 전파해주는 것으로 끝나게 됩니다. 만약 현재 지역과 인접 지역 모두 문명 지역이고 서로 다른 문명을 갖고 있다면, bfs_union과 같이 두 문명을 결합해주면 됩니다.

같은 문명인지 판단하는 것은 find연산을, 문명을 결합하는 것은 union(merge)연산을 사용해 구현할 수 있고, path compression과 union by rank를 이용하면 상수 시간에 근접하게 소요 시간을 줄일 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

int N, K;
int par[100010];
int rnk[100010];
int arr[2010][2010];

void init(){
	for(int i=1; i<=100000; i++) par[i] = i, rnk[i] = 1;
}

int find(int v){
	if(v == par[v]) return v;
	return par[v] = find(par[v]);
}

bool merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return true;

	if(rnk[u] > rnk[v]) swap(u, v);
	par[u] = v;
	if(rnk[u] == rnk[v]) rnk[v]++;
	return false;
}

queue<p> q, qq;
int di[] = {0, 0, 1, -1};
int dj[] = {1, -1, 0, 0};

inline bool can(int i, int j){
	return (0<i && i<=N && 0<j && j<=N);
}

void bfs_union(){
	while(!q.empty()){
		int i = q.front().first;
		int j = q.front().second;
		qq.push(q.front());
		q.pop();

		for(int it=0; it<4; it++){
			int ii = i + di[it];
			int jj = j + dj[it];
			if(!can(ii, jj)) continue;
			if(arr[ii][jj] && arr[i][j] != arr[ii][jj]){
				if(!merge(arr[i][j], arr[ii][jj])){
					K--;
				}
			}
		}
	}
}

void bfs_propagation(){
	while(!qq.empty()){
		int i = qq.front().first;
		int j = qq.front().second;
		qq.pop();

		for(int it=0; it<4; it++){
			int ii = i + di[it];
			int jj = j + dj[it];
			if(!can(ii, jj)) continue;
			if(!arr[ii][jj]){
				arr[ii][jj] = arr[i][j]; q.push({ii, jj});
			}else if(arr[i][j] != arr[ii][jj]){
				if(!merge(arr[i][j], arr[ii][jj])){
					K--;
				}
			}
		}
	}
}

int main(){
	cin >> N >> K;
	for(int i=1; i<=K; i++){
		int a, b; scanf("%d %d", &a, &b);
		arr[a][b] = i;
		q.push({a, b});
	}
	init();
	int ans = 0;
	while(K > 1){
		bfs_union();
		if(K == 1){
			cout << ans; return 0;
		}
		bfs_propagation();
		ans++;
	}
	cout << ans;
}