BOJ 16746 Four-Coloring

문제 링크입니다.

문제 요약

상하좌우 대각선 8방향으로만 간선이 존재하는 평면 그래프를 4색으로 칠하세요.

풀이

답의 존재성은 4색정리에 의해 보장됩니다. 평범한 평면 그래프를 4색으로 칠하는 깔끔한 방법은 아는 게 없으니, 8방향으로만 간선이 있다는 점을 이용해 봅시다.

좌표 순으로 정점을 색칠하면, 어떤 정점을 색칠할 때 그 정점과 연결된 정점 중 색칠된 것은 많아야 4개라는 점을 알 수 있습니다. (글 읽는 방향대로 칠한다고 치면, 왼쪽 위 / 위 / 오른쪽 위 / 왼쪽에 연결된 정점이 해당합니다.) 이 정점들을 칠하는 데 3가지 이하의 색만 사용했다면 이번 정점을 색칠하는 데 별 문제가 안 생깁니다.

문제는 네 정점의 색이 모두 다르게 칠해졌을 땐데, 인접한 정점 색 중 하나를 다른 색으로 바꿔야 됩니다. 한 정점 색을 다른 색으로 바꾸는 작업은 그 두 가지 색 정점만 남긴 그래프에서 해당 정점이 포함된 연결 요소의 색을 싹 다 뒤집어주는 식으로 할 수 있어요. 이때 이 두 가지 색 연결 요소에 바꾸려고 하는 색으로 칠해진, 이번에 칠할 정점이랑 연결된 다른 정점이 붙어있지 않으면 색을 뒤집고 새로 쓸 수 있게 된 색으로 이번 정점을 칠하면 되겠죠.

색을 바꾸려고 봤더니 두 정점이 연결되어 있어서 색을 바꾸나마나한 상황을 생각합니다. 그러면 나머지 두 색 중에 바꿀 수 있는 색이 있어야 할텐데요… 4색정리가 성립하려면 6가지 조합 중 적어도 하나는 가능해야 되지 않을까 싶다는 생각이 스멀스멀 피어오릅니다.

실제로 위의 Claim이 성립해서 사실 그냥 6가지 조합을 다 해보면 답을 맞힐 수는 있습니다. 근데 그게 4색정리의 성립 여부랑 관련이 있냐라고 하면… 그건 아니고요. 대신 주어진 그래프가 평면 그래프의 올바른 임베딩이라는 점을 이용해 증명할 수 있습니다.

왼쪽에 연결된 정점을 위쪽에 연결된 정점의 색으로 바꾸기를 시도합니다. 이게 실패하는 경우는 왼쪽 정점과 위쪽 정점을 연결하는 두 가지 색 체인이 존재할 때 뿐입니다. 여기서 왼쪽 위에 연결된 정점과 오른쪽 위에 연결된 정점을 두 가지 색 체인으로 이을 수 있을까요?

아니요. 왼쪽 위 정점은 체인 안에 갇혀 있고, 오른쪽 위 정점은 체인 밖에 있는 상태로 볼 수 있습니다. 주어지는 그래프가 평면 그래프기 때문에 체인을 이루는 간선을 뚫고 지나갈 수도 없고, 체인 위의 정점은 체인을 이루는 두 색과는 다르기 때문에 체인에 쓸 수 없습니다. 따라서 왼쪽 정점을 위쪽 정점의 색으로 바꿀 수 없다면, 왼쪽 위의 정점을 오른쪽 위 정점의 색으로 반드시 바꿀 수 있습니다.

색 변경은 대충 DFS로 ${\cal O}(N)$에 구현해도 ${\cal O}(N^2)$에 문제를 해결할 수 있습니다. 실제로 구현해 보면 훨씬 빠르게 작동합니다. 그래프 특성 상 ${\cal O}(N)$ 근처까지 깎이는 건가 싶네요.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

struct Vertex{
	int x, y, i;
} v[12345]; int idx[10101], ans[10101];
vector<int> e[10101]; bool vis[10101];

bool dfs(int now, int goal, int tar){
	vis[now] = 1; bool ret = 0; if(now == goal) return 1;
	for(auto& nxt : e[now]) if(!vis[nxt] && ans[nxt] == tar) ret |= dfs(nxt, goal, ans[now]);
	return ret;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){v[i].i = i; cin >> v[i].x >> v[i].y;}
	sort(v+1, v+n+1, [&](Vertex& a, Vertex& b){return a.x*10000+a.y < b.x*10000+b.y;});
	for(int i = 1; i <= n; i++) idx[v[i].i] = i;
	while(m--){
		int u, v; cin >> u >> v; u = idx[u]; v = idx[v];
		e[u].push_back(v); e[v].push_back(u);
	}
	for(int now = 1; now <= n; now++){
		array<int, 5> par = {0,0,0,0,0}, col = {0,0,0,0,0};
		for(auto& nxt : e[now]) if(nxt < now){
			col[ans[nxt]] = 1; int dir;
			if(v[now].y == v[nxt].y) dir = 1;
			else if(v[now].x == v[nxt].x) dir = 3;
			else if(v[now].x-v[nxt].x == v[now].y-v[nxt].y) dir = 2;
			else dir = 4; par[dir] = nxt;
		}
		bool flag = 0; for(int i = 1; i <= 4; i++) if(!col[i]){ans[now] = i; flag = true; break;} if(flag) continue;
		int C = ans[par[1]]+ans[par[3]]; memset(vis, 0, sizeof(vis)); if(!dfs(par[1], par[3], ans[par[3]])) ans[now] = ans[par[1]];
		else{memset(vis, 0, sizeof(vis)); C = ans[par[2]]+ans[par[4]]; dfs(par[2], par[4], ans[par[4]]); ans[now] = ans[par[2]];}
		for(int nxt = 1; nxt < now; nxt++) if(vis[nxt]) ans[nxt] = C-ans[nxt];
	}
	for(int i = 1; i <= n; i++) cout << ans[idx[i]] << '\n';
}