백준12626 Football Team (Large)

작성일 | In

문제 링크

  • http://icpc.me/12626

문제 출처

  • 2009 Google Code Jam Round3 C2번

사용 알고리즘

  • 그래프 컬러링
  • 평면 그래프
  • 4색 정리

시간복잡도

  • O(N2)

풀이

선수들을 정점으로 두고, 다른 색을 입어야 하는 선수를 간선으로 이어주면 그래프가 나옵니다.
만들어진 그래프에서 간선은 교차하지 않으므로 평면 그래프입니다.
평면 그래프에서 인접한 정점을 서로 다른 색으로 칠할 때(Graph Coloring), 최대 4개의 색만 필요하다는 것이 잘 알려져있으므로(4 color theorem), 주어진 그래프가 몇 개의 색깔로 칠할 수 있는지 판단하면 됩니다. 당연히 {1, 2, 3, 4} 중 하나가 정답이 됩니다.

색깔의 개수에 관한 정보

그래프에 간선이 하나도 없다면 1개의 색깔만 있으면 됩니다.
반대로, 간선이 하나라도 존재한다면 최소 2개의 색깔이 필요합니다.

이분 그래프는 두 개의 색깔만 있으면 색칠할 수 있습니다.
반대로, 이분 그래프가 아니라면 최소 3개의 색깔이 필요합니다.

이분 그래프가 아니라는 것을 기하학적으로 나타내면 삼각형이 존재한다는 것입니다.

우리는 ①간선이 존재하는지, ②간선이 존재한다면 삼각형이 존재하는지, ③삼각형이 존재한다면 3개의 색깔로 칠할 수 있는지/4개의 색깔로 칠해야 하는지 판단하면 됩니다.
③를 판단하는 방법을 살펴봅시다.

삼각형

먼저 이분그래프가 아니라면, 그래프에서 영역이 만들어지는 곳은 아래 그림처럼 모두 삼각형입니다.

만약 삼각형에서 두 점의 색깔을 확정했다면 다른 한 점의 색깔은 자동으로 결정됩니다.
이 점을 이용해 재귀적으로 탐색을 하면서 3개의 색깔만으로 칠할 수 있는지 판단하면 됩니다.

또 다른 풀이(듀얼 그래프)

여기에 소개되어 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int n;
int x[1010], y[1010], color[1010];
int g[1010][1010];
int chk[1010][1010];

bool dfs(int u, int v){
	chk[u][v] = chk[v][u] = 1;
	int now = 3 - color[u] - color[v];
	for(int k=1; k<=n; k++){
		if(!g[u][k] || !g[v][k]) continue;
		if(color[k] < 0){
			color[k] = now;
			if(!dfs(u, k) || !dfs(v, k)) return 0;
		}else if(color[k] != now) return 0;
	}
	return 1;
}

void init(){
	memset(color, -1, sizeof color);
	memset(g, 0, sizeof g);
	memset(chk, 0, sizeof chk);
}

void solve(){
	init();
	cin >> n;
	for(int i=1; i<=n; i++) cin >> x[i] >> y[i];

	for(int i=1; i<=n; i++){
		int v[3] = {-1, -1, -1};
		for(int j=1; j<=n; j++){
			if(x[i] >= x[j]) continue;
			int k = y[j] - y[i] + 1;
			if(k < 0 || 2 < k) continue;
			if(v[k] < 0 || x[j] < x[v[k]]) v[k] = j;
		}
		for(int j=0; j<3; j++){
			if(v[j] >= 0) g[i][v[j]] = g[v[j]][i] = 1;
		}
	}
	int ans = 1;

	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(!g[i][j]) continue;
			if(chk[i][j]) continue;
			//exist edge -> 2
			ans = max(ans, 2);
			for(int k=1; k<=n; k++){
				if(!g[i][k] || !g[j][k]) continue;
				//exist triangle -> 3
				ans = max(ans, 3);
				memset(color, -1, sizeof color);
				color[i] = 0, color[j] = 1;
				if(!dfs(i, j)){
					cout << 4 << "\n";
					return;
				}
				break;
			}
		}
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	for(int i=1; i<=t; i++){
		cout << "Case #" << i << ": ";
		solve();
	}
}