[골드 2] 백준 1135 - 뉴스 전하기 (파이썬)

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

풀이

• 회사에는 N명의 직원이 있고, 0번 직원이 사장이다.
• 각 직원은 한 명의 상사를 가지고 있다. (par[i]가 i번 직원의 상사)
• 뉴스는 각 사장(0번)부터 시작해서 전파되며, 각 직원은 동시에 한명에게만 뉴스 전달을 시작할 수 있다.
• 모든 직원이 뉴스를 전달받기까지 걸리는 최소 시간을 구하는 문제이다.

문제는 트리 형태의 구조에서, 루트 노드로부터 모든 노드에게 최대한 빠르게 뉴스를 전파하는 방식으로 시간을 최소화하는 것이다.

서브트리들 간의 전파 순서에 따라 시간 차이가 발생하므로, 더 오래 걸리는 자식부터 먼저 처리하는 것이 유리하다.

child = [[] for _ in range(N)]
for i in range(1, N):
    child[par[i]].append(i)

• child[u]는 u번 직원의 부하들 리스트이다.
• 루트(0번 사장)을 기준으로 하위 트리 구조를 만든다.

D = [0] * N

def dfs(u):
    times = []
    for v in child[u]:
        dfs(v)
        times.append(D[v])
    
    times.sort(reverse=True)

    D[u] = 0
    for i in range(len(times)):
        D[u] = max(D[u], i + 1 + times[i])

• 이 문제는 DFS + DP로 해결이 가능하다.
• D[u]는 u번 노드가 자신의 모든 부하 직원들에게 뉴스를 전하는데 걸리는 최소 시간이다.
• 자식 노드들을 몰면서 D[v]값을 모은다.
• 시간이 오래 걸리는 자식에게 먼저 뉴스를 전달하면 전체 시간이 최소화된다.

예를 들어서 입력과 구조에 대해서 작성한다.

4
-1 0 0 1

이런 입력이 있을 때 트리의 구조는 다음과 같다.

     0
    / \\
   1   2
  /
 3

• 전파 순서를 확인하면,
  • 0번에서 1, 2에는 동시에 전파된다.
  • 1번에서 3에 전파한다.
• 각 시간을 확인하면
  • 0번에서, 1, 2에는 1초
  • 1번에서 3에는 1초
  • 총 2초가 사용된다.

코드

# 백준 1135 - 뉴스 전하기
# 분류 : 다이나믹 프로그래밍

N = int(input())
par = list(map(int, input().split()))

child = [[] for _ in range(N)]
for i in range(1, N) :
    child[par[i]].append(i)

D = [0] * N

def dfs(u) :
    # D[u] 의 값을 구하는게 최종 목표

    times = []
    for v in child[u] :
        dfs(v)
        times.append(D[v])
    
    times.sort(reverse=True)

    D[u] = 0
    for i in range(len(times)) :
        D[u] = max(D[u], i + 1 + times[i])

dfs(0)
print(D[0])