[BOJ] 1693번: 트리 색칠하기

https://www.acmicpc.net/problem/1693

4색 문제에 의해 임의의 평면그래프는 4개의 색으로 인접한 node끼리 색이 겹치지 않게 만들 수 있고, 특히 트리의 경우 단 2가지 색으로 색이 겹치지 않게 할 수 있습니다. 그렇지만 2가지 색으로 칠하는 것이 최소값이라는 보장을 할 수가 없기 때문에, 결국 DP를 이용해서 해결을 해야하는데 사용할 수 있는 색이 100000개이기 때문에 정직하게 DP를 하면 O(N^2)으로 시간 내에 풀 수가 없습니다.

그런데 100000개의 node를 최소 cost로 칠할 때 과연 몇개의 색이 필요할까를 생각해보면 의외로 적은 수의 색이 필요합니다. (koosaga님의 답변을 보고 알아낸 사실입니다.)

$S(N)$ = 반드시 N개의 색을 써야 최소 cost로 색칠할 수 있는 그래프의 node 갯수 중에 최소

$S(1) = 1, S(2) = 2$ 입니다.

만약 $S(i) > 100000$ 이라면 색깔 1, 2, 3, .. , $i-1$ 까지로만 tree를 색칠하면 될 것입니다.

이제 $S(N)$을 구하기 위해 N개의 색을 써야 최소 cost로 색칠할 수 있는 임의의 그래프를 생각해봅시다. 그 그래프 안에서 색깔 $N$으로 칠해진 node는 반드시 존재해야합니다. 그 node를 $A$라고 할 때, $A$의 subtree 들을 생각해봅시다.

subtree $T_1$, $T_2$, .. , $T_i$의 root들을 생각해보면 그 중에서 색깔 1부터 $N-1$까지 전부 적어도 한 번씩은 등장해야합니다. 그렇지 않다면 굳이 $A$를 색깔 $N$으로 칠할 이유가 없기 때문입니다.(예를 들어 색깔 1이 $T_1$, .. ,$T_i$의 root에 등장하지 않으면 $A$를 색깔 $N$으로 칠하지 말고 1으로 칠하는 것이 더 cost가 낮음)

그러면 $N$개의 색을 써야 최소 cost로 색칠할 수 있으면서 가장 node의 수가 적은 그래프는 아래와 같은 모양을 가졌을 것입니다.

그리고 S의 정의에 의해 $T_i$의 원소의 갯수는 $S(i)$ 이상입니다.

그러면 $S(N) \geq S(1) + S(2) + .. + S(N-1) + 1$이 되고 $S(1) = 1, S(2) = 2$으로 계산해보면 $S(N) >= 2^{N-1}$이라는 식을 얻을 수 있습니다. 그리고 $2^{16} < 100000 < 2^{17}$ 이므로 18개의 색으로 최대 100000개의 node를 가지는 graph를 최소 cost로 색칠할 수 있음이 보장됩니다. 물론 실제 $S(N)$은 $2^{N-1}$보다 훨씬 클 것입니다. 당장 $S(3)$만 해도 확실히 4보다는 크기 때문입니다. 그렇기에 18개보다 더 적은 색이 필요할테지만 18개 정도로 해도 시간 내에 풀이하기에는 충분합니다.

그러면 이제 1번을 root로 해서 tree를 재구성하고, 말단부터 $D$ table을 채워나가면 됩니다. $D$ table은 $D[100004][MAX\_COLOR + 1]$이고, $D[i][color]$ : 나의 부모의 색깔이 color일 때 i번째 node를 root로 하는 subtree의 최솟값. color = 0이면 부모가 없는 경우를 의미합니다.

https://github.com/encrypted-def/BOJ/blob/master/1693.cpp