[백준] 1135. 뉴스 전하기

문제

백준  뉴스 전하기 https://www.acmicpc.net/problem/1135

 

코드

n = int(input())
parent_list = list(map(int, input().split()))
child_list = [list() for _ in range(n)]

for child in range(1, n) :
  parent = parent_list[child]
  child_list[parent].append(child)

def dfs(node) :
  if not child_list[node] :
    return 0
  result = list()
  for child in child_list[node] :
    result.append(dfs(child))
  result.sort( reverse = True)
  result = [ result[i] + i + 1 for i in range(len(child_list[node])) ]
  return max(result)

print(dfs(0))

 

풀이

• 그리디하게 트리를 순회한다.
• 전화를 받은 부하직원은 자기 부하에게 전화를 할 수 있게 된다. 따라서 전화를 모두 돌리는데 시간이 오래 걸리는 직원부터 전화를 돌리는게 더 시간효율적이다.
• 모든 결과를 받아서 정렬하면 i번째 직원이 자신의 부하직원에게 전화를 돌리는데 걸리는 총 시간은 (부하 직원 자체가 전화에 소모하는 시간 ) + (i + 1) 이 된다. 
• 이를 재귀적으로 모든 노드에 대해 적용하여 정답을 구한다.