[백준 1135] - 뉴스 전하기

내가 당분간은 그래프, 트리 문제 안푼다고 했는데...

1135번: 뉴스 전하기

문제

민식이 부터 말단 사원 까지 소식을 전파했을 때 걸리는 시간의 최솟값을 구하는 문제 입니다. 착각하기 쉬운 점이 있다면 현재 위치의 간부가 부하들에게 전파를 할 때, 모든 부하들을 전파한 다음, 부하들이 전파를 하는 것이 아니라 간부가 부하 1명에게 전파를 하면 그 다음에는 간부가 아직 전파하지 않은 부하에게 전파함과 동시에 이미 전파된 부하도 같이 자신의 부하에게 전파를 하게 됩니다. 아래의 그림 처럼요.

2명 이상의 직원들이 동시에 전파할 수 있습니다.

접근

빠른 시간안에 전파하는 방법을 찾는 문제는 간단합니다. 더 많은 숫자의 사원들이 전파를 할 수록 전파는 더 빨리 끝납니다. 더 많은 사원들이 전파를 하려면 간부가 전파 시간이 오래 걸리는 순으로 사원들에게 전파하면 됩니다. 그렇다면 루트에서 내려오는 방식으로 루트 지점에서 자식 노드 중 오래 걸리는 순으로 정렬해서 탐색해야 하는데 문제는, 자식 노드들이 전파 시간이 얼마나 되는 지 전혀 모릅니다. 따라서 루트 지점에서 각 하위 노드들을 전부 탐색해서 시간을 계산한 다음 하위 노드들의 전파 시간을 이용해서 루트의 전파 시간을 계산합니다. 

결국 하위 노드들과 관련된 데이터들을 이용해서 루트의 관련 정보를 구하는 방식이기 때문에, 작은 문제들 부터 하나 씩 풀어가기 때문에 상향식 다이나믹 프로그래밍(타뷸레이션(Tabulation))을 사용하고 자식 노드들을 전부 탐색한 다음 작업을 진행하기 후위 탐색을 진행하게 됩니다. DP같은 경우, 일반적인 배열이 아닌 트리 구조에서의 DP를 사용하기 때문에 트리 DP라고도 합니다.

사실 DP 말고도 순수 DFS로도 푸는 방법이 있지만. 저는 트리 DP를 처음 써보는 입장이기 때문에 DP를 사용해서 풀었습니다.

알고리즘

알고리즘 자체는 간단합니다. 위에서 설명한 대로 후위 탐색을 진행하고 자식 노드들을 전부 순회해서 자식 노드에서의 최소 전파 시간들을 구한 다음에 이 전파시간들을 가장 오래 걸리는 순으로 정렬한 다음, 루트의 전파 시간을 계산합니다. 문제는 최소 전파 시간은 어떻게 계산하느냐 입니다.

def func(u):
    orders = []
    for v in T[u]:
        # 자식 노드들을 순회해서 최소 전파시간 구하기
        func(v)
        orders.append((v, dp[v]))
    if T[u]:
        # 가장 시간 많이 걸리는 것부터 탐색
        orders.sort(key=lambda e: -e[1])
        for i in range(len(orders)):
            # i <- 탐색 순서 i+1이 루트에서 자식 까지 전파하는 데 걸리는 시간
            dp[u] = max(dp[u], orders[i][1] + i + 1)

func(u)는 u에서의 최소 전파 시간을 구하는 함수 입니다. 맨 아랫줄이 핵심인데 orders[i][1]가 자식 노드의 최소 전파 시간인데 거기에 i + 1이 붙어 있습니다. 이 i + 1은 루트 노드가 탐색한 순서로 맨 처음에 탐색했을 경우, 1분 안에 해당 자식 노드에 전파했으므로 orders[i][1]에 1이 붙고 두 번째로 탐색을 했으면 루트에서 자식 까지 탐색하기 까지 걸린 시간이 2분이므로 2가 붙습니다. 결국 i번째에 전파된 노드는 루트부터 노드 까지 걸린 전파 시간이 i + 1이 되므로 orders[i][1] + i + 1이 됩니다.

아까 설명한 대로 자식 노드에게 한번 전파를 한 이후에 바로 자식 노드들이 전파를 시작하기 때문에 dp[u]에 자식노드 까지 걸리는 시간을 합하지 않고 자식 노드까지의 시간들 중 가장 나중에 전파가 끝나는 자식 노드의 시간으로 설정합니다.

전체 코드(Python)

import sys
import collections
input = sys.stdin.readline

N = int(input())
A = list(map(int, input()[:-1].split()))
T = [list() for _ in range(N)]
dp = [0] * N

for v, u in enumerate(A):
    if v == 0:
        continue
    T[u].append(v)

def func(u):
    orders = []
    for v in T[u]:
        func(v)
        orders.append((v, dp[v]))
    if T[u]:
        # 가장 시간 많이 걸리는 것부터 탐색
        orders.sort(key=lambda e: -e[1])
        for i in range(len(orders)):
            dp[u] = max(dp[u], orders[i][1] + i + 1)
func(0)
print(dp[0])

아이디어까지는 쉽게 생각해 냈는데 이를 구하는 방법을 찾는데는 좀 걸린 것 같습니다. 반례를 생각 안하고 무지성으로 제출하다보니 이 꼬라지가 났네요. 다음부터는 반례 끝까지 찾아보고 제출해야겠습니다. 트리 DP를 예전부터 어려워 하고 있었는데 이 문제 덕분에 트리 DP을 쉽게 배울 수 있었습니다.