[백준] 1693 트리 색칠하기

October 14, 2020

문제 링크

1693 트리 색칠하기

알고리즘

트리 DP

풀이

최소 비용으로 N개의 정점으로 이루어진 트리를 겹치지 않게 색칠하기 위해선 최대 log₂N개의 색깔이 필요하다.

위의 힌트는 koosaga님의 답변을 통해 알았다. 이를 통해 dp의 크기를 정하고 단말 노드부터 메모이제이션을 통해 차례로 갱신해나가면 된다. 여기서 시간 복잡도는 O(N(logN)²)이다.

dp[root][color]: root 노드의 색깔이 color일 때, 서브트리의 최소 비용

코드

import sys
from math import log2
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def dfs(root):
    visited[root] = True
    for c in graph[root]:
        if visited[c]:
            continue
        dfs(c)
        # i: root color, j: child color
        for i in range(1, MAX):
            dp[root][i] += min(dp[c][j] for j in range(1, MAX) if j != i)
    for i in range(1, MAX):
        dp[root][i] += i

n = int(input())
MAX = int(log2(n+1)) + 1
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
dp = [[0] * MAX for _ in range(n+1)]

for _ in range(n-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

dfs(1)
print(min(dp[1][1:]))

Written by@WOOJIN

自强不息,厚德载物

GitHub