[백준/1135] 뉴스 전하기 (Python)

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

1135번: 뉴스 전하기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:11:19

 

---

 

문제 설명

 

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

 

입력 및 출력

 

입력

 

첫째 줄에 직원의 수 N이 주어진다. 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수이다. N은 50보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력한다.

 

입력 예시

 

24
-1 0 0 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 12 13 14 16 16 16

 

출력 예시

 

7

 

 

---

 

풀이

 

트리 순회를 하되, 다음과 같이 그리디하게 생각해볼 수 있다.

 

• 만약 자기에게 부하 직원이 없다면(리프 노드) 걸리는 시간은 0이다.
• 상사 자신이 다른 부하 직원에게 전화를 돌릴 때, 이미 전화한 부하 직원은 본인의 부하 직원에게 전화를 돌릴 수 있다. 따라서 전파에 시간이 오래 걸리는 직원부터 돌리는 게 효율적이다. 모든 결과를 받아 정렬하도록 하자.
• 그렇다면, i번째(0 <= i) 부하 직원이 소요되는 총 시간은 (부하 직원 자체가 전화에 소모하는 시간) + (i + 1) 이 된다. 상사가 부하 직원에게 전화할 때마다 1분씩 소요되기 때문이다.
• 즉 계산된 총 시간 중 가장 많은 시간이 소요되는 경우가 이 상사의 소요 시간이 된다. 이를 재귀적으로 모든 노드에 대해 적용한다.

 

 

풀이 코드

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))

풀이 완료!