1135번 - 뉴스 전하기(python3)

문제 링크: https://www.acmicpc.net/problem/1135

1135번: 뉴스 전하기

지난번 사회망 서비스(SNS) 문제에 이어 다시 트리DP를 이용해 푸는 문제입니다.

 

회사 내 상사-부하직원 관계가 트리 모양으로 주어져 있습니다. 0번 노드가 회사 내 root 역할을 하고, 나머지 직원들은 모두 1명의 직속 상사만 존재합니다. 0번 노드를 제외한 모든 직원은 0번 노드의 직속/간접 부하라고 생각하면 됩니다.

 

0번 노드에 어떤 정보가 들어가서 모든 직원에게 알리고 싶은데, 자신의 직속 부하에게만 1번에 1명씩 연락이 가능하고, 연락하는데 걸리는 시간은 1분입니다. 내 밑에 4명의 직속 부하가 있다면 이들에게 모두 정보를 전하는데 걸리는 시간은 4분입니다. 트리가 주어졌을 때 모든 직원에게 정보를 전달하는데 걸리는 최소 시간을 계산하면 됩니다.

 

지난번에는 현재 노드 v가 얼리어답터인지 아닌지 총 2가지 경우를 계산해야했는데, 이번에는 그럴 필요 없이 그리디하게 접근하면 됩니다. 다음은 문제 푸는데 사용한 코드입니다.

현재 노드 v의 child로 a, b, c가 있다고 할 때, 각 child를 root로 하는 subtree에 정보를 모두 전달하는데 걸리는 시간이 큰 쪽부터 먼저 전화를 돌리는 것이 효율적입니다. time[a], time[b], time[c]값을 기준으로 전화 순서를 정하고, 그 중 가장 큰 값을 time[v]에 assign해주면 됩니다. 전체 트리의 root node는 정보를 가진 상태에서 시작하므로 알고리즘 수행이 끝난 후 time[0]에서 1 뺀 값을 출력해주면 됩니다.