트리에서의 다이나믹 프로그래밍 1편

1. 문제 정보

BOJ 1693 - 트리 색칠하기 Platinum 2

 

2. 풀이

쉬운 듯 어려운 듯한 문제였습니다.

 

반례를 못 찾았다면 못 풀었을 것 같습니다. 그래도 예시가 친절해서 삽질을 안 할 수 있었던 문제였습니다.

 

[접근 1] 무조건 두 가지 색깔로 칠하는 게 최적의 해 아닐까?

아래는 문제에서 주어진 트리를 시각화 한 그림입니다.

문제에서 주어진 예시

 

매우 다행히도 제 첫 번째 접근이 틀렸음을 예시가 말해주고 있어서 바로 다른 풀이로 틀 수 있었습니다.

 

1과 2로 모든 정점을 색칠한다면 차수에 따라 색깔이 칠해지게 되고, 루트 정점에 1이 칠해지는 경우와 2가 칠해지는 경우 두 가지 밖에 없습니다.

위 그림에서 두 가지 경우를 모두 볼 수 있는데, 둘 다 최적의 해가 아님을 쉽게 파악할 수 있습니다.

 

주어진 예시에서는 5번 정점에 3을 칠하고, 1번 정점에는 2, 나머지 정점에는 1을 칠하는 것이 최적의 해입니다.

 

그러면 1과 2로만 채우는 것이 최적의 해아 아님을 깨달았는데, 어떻게 색깔을 칠해야 할까요?

그렇다고 n개의 색깔에 대해 모든 경우를 계산하는 것도 시간 복잡도가 O(n2)이 되어 시간 초과가 날 것이라는 것도 직감적으로 알고 있었죠.

 

근데 아무리 보아도 최대 100,000개의 색깔을 쓸 필요가 없다고 생각했습니다.

[접근 2] 색깔을 모두 사용할 필요 없이 어느 순간부터 답이 항상 존재하지 않는 임계점이 있지 않을까?

따라서 비용이 어느 순간부터 계속 증가하는 임계점이 있을 것이라고 생각하여 그 임계점을 찾는 방향으로 풀이를 바꿨습니다.

고맙게도 문제에 제시된 예시 덕분에 해결의 실마리를 찾을 수 있게 되었습니다.

 

특정 차수에 k개의 노드가 있다면 그보다 한 단계 낮은 차수에 k + 1개의 노드가 있는 트리가 색깔을 최대한으로 사용하는 트리의 예시라고 생각했습니다.

 

만약 특정 차수에 k개의 노드가 있고, 한 단계 낮은 차수에 k + 2개 이상의 노드가 있는 트리의 경우에는 최적의 해가 사용하는 색깔이 변하지 않는다는 것도 직관적으로 인지할 수 있었습니다.

 

따라서 현재 차수에 있는 정점의 개수가 k일 때,

- 차수 (현재 차수 - 1)에 있는 정점의 개수가 k + 1 이상이면 최대 개수의 색깔을 사용해야 한다.

- 차수 (현재 차수 - 1)에 있는 정점의 개수가 k 이하이면 최대 개수의 색깔을 사용하지 않아도 된다. 

와 같이 정리할 수 있습니다.

규칙을 파악하고 나니 임계점을 찾는 것은 그리 어렵지 않았습니다.

 

[2개의 색깔을 사용하는 경우]

차수 t에 k개의 정점, 차수 t - 1에 k + 1개의 정점이 존재하므로 총 2k + 1개의 정점이 존재합니다.

 

[3개의 색깔을 사용하는 경우]

차수 t - 1에 2k + 1개의 정점, t - 2에 2k + 2개의 정점이 존재하므로 총 4k + 3 개의 정점이 존재합니다.

 

…

 

이런 방식으로 색깔의 종류에 따른 총 노드 개수를 계산합니다.

그러면 k가 루트 노드가 되는, 즉 k == 1일 때 처음으로 총 노드의 개수가 100,000을 넘어간다면, 그 때의 색깔의 종류 개수가 임계점이 됩니다.

 

…

 

[17개의 색깔을 사용하는 경우]

총 노드 개수 217k - 1

 

이 경우에는 k가 1이면 최대 노드 개수인 100,000을 넘어가므로 최소 비용은 항상 최대 17가지의 색깔 안에서 나온다고 계산할 수 있었습니다.

 

감이 좋으신 분이라면 저처럼 직접 계산을 하지 않고도 최대 log n 개의 색깔 내에서 항상 나온다는 것을 알 수 있었을 것입니다.

따라서 DP 배열을 dp[100000][100000]에서 dp[100000][18]로 줄여 대략 O(nlogn)의 시간 복잡도를 가질 수 있도록 줄여주었습니다.

 

3. 코드

풀이를 떠올렸다면 푸는 것은 그리 어렵지 않습니다.

전형적인 재귀 DP로 풀이하면 쉽게 맞을 수 있습니다.

 

주의할 점은 색깔이 여러 개 있기 때문에 자식 정점에 여러 번 방문할 수 있습니다.

이전 정점을 저장하여 부모 정점은 방문하지 않고, 자식 정점은 가능한 모든 색깔에 대해 모두 살펴볼 수 있도록 해야 합니다.

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e5 + 6;
const int INF = 0x7FFFFFFF;

int n;
vector<int> v[SIZE];
int dp[SIZE][18];

int dfs(int now, int color, int prev){
    int& ret = dp[now][color];
    if(ret != -1) return ret;
    
    ret = color;
    for(int next: v[now]){
        if(prev == next) continue;
        
        int temp = INF;
        for(int i = 1; i < 18; i++){
            if(i == color) continue;
            temp = min(temp, dfs(next, i, now));
        }
        ret += temp;
    }
    
    return ret;
}

int main(){
    memset(dp, -1, sizeof(dp));
    
    cin >> n;
    for(int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        v[x].push_back(y); v[y].push_back(x);
    }
    v[0].push_back(1); v[1].push_back(0);
    
    cout << dfs(0, 0, 0);
    
    return 0;
}

---

솔직히 엄밀한 수학적 정의보다는 직관으로 풀 수 있었던 문제가 아닌가 싶습니다.

(솔직히 증명 과정이 정확히 맞는 지도 모르겠네요.)

만약 대회에서 이 문제를 만났다면 시간 복잡도가 O(n) ~ O(nlogn) 사이임을 알아채고 색깔을 nlogn 크기로 조정하여 제출했을 것 같습니다.

 

세심한 관찰과 어느 정도의 직관, 그리고 사고력을 요구하는 좋은 문제였다고 생각합니다.

---

제 글이 많은 도움이 되었길 바라며,
긴 글 봐주셔서 감사합니다!
멋진 개발자가 되기 위해 더 열심히 달리겠습니다!
- 달맹 -