[BOJ 1693 // C++] 트리 색칠하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1693번 문제인 트리 색칠하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1693

1693번: 트리 색칠하기

이 문제에서는 인접한 노드에 다른 색을 칠하면서 사용한 비용이 최소가 되게 트리의 노드를 색칠해야 한다.

이 문제를 풀기 위해 가장 먼저 생각해야할 것은 "최대 몇 개의 색이 필요할 것인가"이다.

문제에 나와있는 것과 같이 N개의 노드에 N가지 색을 칠하는 경우를 모두 조사하려면 시간과 메모리가 불필요하게 많이 들기 때문이다.

 

다음과 같은 관찰을 하자.

1) 색을 한 종류 사용하여 최소비용인 경우가 등장하는 트리는 최소 1개 노드, 2개를 사용하여 최소비용인 경우가 등장하는 트리는 최소 2개의 노드가 있어야 한다.

2) 함수 f(n)을 "색을 n 종류 사용하여 최소비용인 경우가 등장하는 트리가 가지고 있어야 할 최소 개수의 노드"로 정의하자. 1에 의햐여 f(1) = 1, f(2) = 2 이다.

3) f(i)는 f(i-1)+f(i-2)+...+f(2)+f(1) 보다 크거나 같다. 그 트리를 i가지 색으로 칠하는 것이 최소비용이라면 비용이 i인 색을 다른 색으로 바꿀 수 없어야 하고, 그렇다면 i번째 색을 칠해야하는 노드에는 i-1, i-2, ..., 2, 1의 비용이 들어가는 색을 가진 노드가 각각 인접해있어야 하기 때문이다.

4) 2, 3의 관계식을 이용하면 f(i)는 2^(i-2)보다 크거나 같음을 알 수 있다.

 

4의 관계식에 따라, 이 문제의 범위(노드 10만개)에서는 색을 많아야 18가지만 사용할 것이라는 것을 알 수 있다. 실제로 18개보다 더 적은 색만을 이용할 가능성도 있기는 하지만(정확한 bound가 아니므로), 이 정도로 범위를 축소한 것 만드로도 문제를 푸는 데에는 충분하다.

 

남은 것은, 리프노드서부터 각 노드를 i(1 이상 18이하)로 칠할 때 그 노드를 루트로 하는 부분트리를 칠하는 최소비용을 기록해나가는 것이다.

탐색을 마치면, 루트로 정한 노드를 살펴 각 색깔별로 칠해져있는 경우의 최소비용들 가운데 최솟값을 출력하면 된다. 

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin; using std::cout;
using std::vector;

int arr[100001][19]; // arr[i][j]: j색으로 칠한 i번 노드를 루트로 갖는 부분트리의 비용최솟값
vector<int> G[100001];

void dfs(int root, int parent) {
    vector<int>::iterator iter = G[root].begin();
    for (;iter != G[root].end();iter++) {
        if (*iter == parent) continue;
        dfs(*iter, root);

        int s1, s2;// s1: 가장 작은 것, i1: s1의 index, s2: 두번째로 작은 것
        int i1;
        if (arr[*iter][1] < arr[*iter][2]) {
            s1 = arr[*iter][1], i1 = 1, s2 = arr[*iter][2];
        }
        else s1 = arr[*iter][2], i1 = 2, s2 = arr[*iter][1];
        for (int i = 3;i < 19;i++) {
            if (arr[*iter][i] <= s1) {
                s2 = s1;s1 = arr[*iter][i];
                i1 = i;
            }
            else if (arr[*iter][i] < s2) {
                s2 = arr[*iter][i];
            }
        }
        for (int i = 1;i < 19;i++) {
            if (i != i1) arr[root][i] += s1;
            else arr[root][i] += s2;
        }
    }
}


int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    for (int i = 1;i <= N;i++) { // arr 초기화: 각 j번째 성분은 그 노드를 j색으로 칠하므로
        for (int j = 1;j <= 18;j++) {
            arr[i][j] = j;
        }
    }
    for (int i = 1;i < N;i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1, 0);
    int ans = arr[1][1];
    for (int j = 2;j <= 18;j++) {
        if (ans > arr[1][j]) ans = arr[1][j];
    }
    cout << ans;

    return 0;
}