[백준][Python] 1135번 뉴스 전하기 - 골드 2

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

 

 

문제

 

풀이

깊이 우선 탐색과 DP를 활용하여 문제를  풀어주었습니다.

DFS방식을 사용하여 리프 노드에 도달한 뒤, 리프 노드에서부터 오름차순으로 걸리는 시간을 계산해줍니다.

 

코드

# 1135번 뉴스 전하기
num = int(input())
order = list(map(int, input().split()))
tree = [[] for _ in range(num)]
for idx, manager in enumerate(order):
    if idx != 0:
        tree[manager].append(idx)
dp = [0 for _ in range(num)]
def dfs(node):
    node_to_sub = []
    for sub in tree[node]:
        dfs(sub)
        node_to_sub.append(dp[sub])
    
    # 만일 부하직원이 존재한다면
    if node_to_sub:
    	# 걸리는 시간을 내림차순으로 정렬
        node_to_sub.sort(reverse=True)
        # 리프노드까지의 뉴스 도달 시간이 많이 걸리는 부하직원부터 전달해준다.
        # idx => 뉴스를 전달받는 부하 직원 순서, 뉴스를 전달 받는데 걸리는 대기시간을 뜻한다.
      	# amount => 직속 부하 직원으로부터 말단 직원(리프 노드)까지 뉴스가 도달하는데 걸린 시간.
        choose_large_time = [amount + idx + 1 for idx, amount in enumerate(node_to_sub)]

        maximum_time = max(choose_large_time)
        dp[node] = maximum_time

dfs(0)
print(dp[0])

 

 

출력결과