[BOJ] Q1135 뉴스 전하기

[BOJ] Q1135 뉴스 전하기

Question

Language: Python

Difficulty: Gold 2

Tree + DP 결합한 형태의 유형의 문제로, Top-Down 접근 방식을 고려하여 문제 풀이를 진행한다. 각각의 자식 노드에 대해서 해당 자식 노드를 처리하기 위한 시간을 파악해서 가장 많이 걸리는 시간을 해당 노드의 처리 시간으로 저장한다.

모든 사람들에게 뉴스를 전달하기 위한 시간의 최솟값을 구하는 것이 목표이므로, 시간이 가장 오래 걸리는 자식 노드를 먼저 처리하기 위해 다음과 같이 정렬을 수행하고, 정렬 순서 + 해당 자식 노드 처리 시간이 가장 높은 값을 구한다.

childs.sort(reverse=True)
#가장 오래 걸리는 시간 값을 저장한다.
dp[vertex]=max([childs[i] + i+1 for i in range(len(childs))])

Solution

import sys

def solution(vertex):
    global dp

    childs=[]
    #자식이 있으면 계속 내려간다.
    if tree[vertex] != []:
        for adj_vertex in tree[vertex]:
            solution(adj_vertex)
            #자식 노드가 처리가 되면 자식 노드가 처리 되기 위한 시간 값을 저장
            childs.append(dp[adj_vertex])
    #더 이상 자식이 없는 경우
    else:
        return 0
    #시간이 많이 걸리는 자식을 먼저 처리할 수 있도록 한다.
    childs.sort(reverse=True)

    #가장 오래 걸리는 시간 값을 저장한다.
    dp[vertex]=max([childs[i] + i+1 for i in range(len(childs))])
    return dp[vertex]

if __name__ == '__main__':
    n=int(input())
    child_infos=list(map(int,input().split()))
    tree=[[] for _ in range(n)]

    for child in range(1,n):
        parent=child_infos[child]
        tree[parent].append(child)
    
    dp=[0] * n
    solution(0)
    print(dp[0])