백준 1135 : 뉴스 전하기

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

1135번: 뉴스 전하기

 

해결 방법 : DFS

• 직원 조직도 트리를 구성한 뒤에, 각 노드에서 자신의 부하 직원들이 소요하는 시간을 구하며 상향식으로 값을 구해나갔다.
• 부하 직원들의 소요시간이 클 수록 먼저 전화하는게 이상적이며, 그렇다고 해서 이들 중 가장 큰 시간 + 1이 현재 매니저 직원의 소요시간이 된다고 판단하면 안된다.
  • 만약 [1, 49, 49, 49, 50] 으로 부하 직원들의 소요시간이 구성되었다고 한다면, 해당 매니저 직원의 소요시간은 52(부하) + 1(매니저)로 53이 되야함을 생각하면 된다. 
  • 따라서 부하직원들의 소요 시간을 담은 리스트 required를 내림차순 정렬한 뒤에, 각 요소에 인덱스를 더해주어 현재 매니저가 각 부하직원들에게 전화를 돌리는 시간을 합산해주었다. 이후의 max(required) + 1이 현재 매니저 직원의 소요시간이 된다.

 

import sys
input = sys.stdin.readline
from collections import defaultdict, deque

def solution(N, bossList):
    T = defaultdict(list)

    for i, boss in enumerate(bossList): # 조직도 트리 초기화
        T[boss].append(i)

    def dfs(boss):
        if T.get(boss) is None: # 말단 부하 소요시간 1
            return 1

        required = [] # 부하 직원들의 소요시간
        for emp in T[boss]:
            required.append(dfs(emp))

        required.sort(reverse=True) 
        required = [t + i for i, t in enumerate(required)] # 전화 통화 순서에 따라 추가 시간 합산
        return max(required) + 1 # 부하직원으로 부터의 최대 소요시간 + 자신의 소요시간

    return dfs(0) - 1

if __name__ == '__main__':
    N = int(input())
    bossList = list(map(int, input().split()))
    result = solution(N, bossList)
    print(result)