[BOJ] 1135 - 뉴스 전하기 (Python)

 

 

아이디어

 

DFS로 말단 직원에서부터 자신의 부하들에게 전화하는 데 걸리는 가장 긴 시간을 DP로 구해 나간다.

 

 

풀이

 

상사 번호를 리스트 P에 저장하고, 부하 직원의 번호를 상사 번호에 맞게 2차원 리스트 child에 저장한다.

 

함수 dfs에서는 자식 노드들을 탐색하여 구한 자식 노드에서 가장 오래 걸리는 시간을 빈 리스트 temp에 추가한다.

내림차순 정렬한 temp의 각 요소들과 그 순번을 더한 값 중 최댓값을 해당 노드에서 가장 오래 걸리는 시간으로 저장한다.

리프 노드에서는 자식 노드가 없어 temp가 빈 리스트이므로 for문과 if문 진입 없이 함수가 종료된다.

 

0번 직원부터 함수 dfs를 호출한 후 0번 직원의 dp 테이블에 저장된 결과값을 출력한다.

 

def dfs(idx):
    temp = []
    for i in child[idx]:
        dfs(i)
        temp.append(dp[i])
    if temp:
        temp.sort(reverse=True)
        time = [temp[i]+i+1 for i in range(len(temp))]
        dp[idx] = max(time)

N = int(input())
child = [[] for _ in range(N)]
P = list(map(int, input().split()))
for i in range(1, N):
    child[P[i]].append(i)
dp = [0]*N
dfs(0)
print(dp[0])