1814 - 지붕 색칠하기

문제 링크

---

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

문제 요약

---

크기가 \(N\)인 트리가 주어진다. 이 트리의 정점들을 \(M\)가지의 색으로 칠하려고 하는데 각각의 색들은 색을할 할 때 비용이 든다. 또한 인접한 정점은 서로 색이 달라야 한다. 제약조건을 지키면서 모든 정점들을 칠할 때 드는 최소 비용을 구하는 문제다.

문제 풀이

---

주어지는 입력이 트리이기 때문에 \(dp\)로 쉽게 풀릴것 같은 생각이 든다. 아래와 \(dp\ table\)을 생각해보자.

\(dp[here][color]=\ \)\(here\)를 \(color\)로 색칠하고 \(here\)의 \(subtree\)를 색칠하는데 드는 최소 비용

이 식은 어떻게 채워질 수 있을까? 이식은 아래와 같을 것이다.

\(dp[here][color]=\sum_{each\ child} (\min_{\ i \in M, i \ne color} dp[child][i])\ +\ cost[color]\)

이런 점화식을 통해 임의의 루트를 잡고 답을 구할 수 있다. 하지만 이 설계에는 큰 문제가 있다. 바로 \(M\)이 너무 크다는 것이다. 이대로 계산을 하게 되면 전체 시간복잡도는 \(O(NM^2)\)이 되서 시간내에 답을 구할 수 없다.

그렇다면 이 식을 개선시킬 수 있는 방법이 있을까? 여기에 4색 정리를 끼얹어 보자. 4색 정리는 간단하게 설명하자면 평면 그래프에서 모든 정점을 전부 색칠하기 위해서는 네가지 색으로 충분하다는 것이다. 우리가 계산해야 하는것은 트리고 트리는 평면 그래프중 하나다. 그렇다면 \(M\)개의 색을 모두 사용할 필요가 없고 그 중에 가장 싼 네가지 색만 사용한다는 전략을 사용하면 최적의 답을 구할 수 있을거라는 생각을 할 수 있다.

그렇다면 전체 시간복잡도는 \(O(4^2N)\)이 되고 시간내에 충분히 들어온다.

(불가능한 경우도 따로 처리해줘야 할까 했지만 주어지는 입력은 항상 가능한 경우만 들어오는 것 같다.)

소스 코드

---

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 987654321;
const int MAX = 10010;
int n, m, u, v, C[MAX], dp[MAX][4];
vector<vector<int>> node;

int func(int parent, int here, int color) {
  int& ret = dp[here][color];
  if (ret != -1) {
    return ret;
  }
  
  ret = 0;
  for (int there : node[here]) {
    if (there != parent) {
      int child = INF;
      for (int j = 0 ; j < min(4, m) ; ++j) {
        if (j != color) {
          child = min(child, func(here, there, j) + C[j]);
        }
      }
      ret += child;
    }
  }
  
  return ret;
}

int main() {
  scanf("%d", &n);
  node.resize(n);
  for (int i = 0 ; i < n - 1 ; ++i) {
    scanf("%d%d", &u, &v);
    node[u - 1].push_back(v - 1);
    node[v - 1].push_back(u - 1);
  }
  scanf("%d", &m);
  for (int i = 0 ; i < m ; ++i) {
    scanf("%d", &C[i]);
  }
  sort(C, C + m);
  
  memset(dp, -1, sizeof(dp));
  int ans = INF;
  for (int i = 0 ; i < min(4, m) ; ++i) {
    ans = min(ans, func(0, 0, i) + C[i]);
  }
  
  printf("%d\n", ans);
}