[BOJ] 1135 뉴스전하기 (Python3)

1 분 소요

문제

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

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

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

입력

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

출력

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
n = int(input())
infos = list(map(int, input().split()))


graph = dict()

for i in range(n):
    graph[i] = []
    
for i, info in enumerate(infos):
    if info != -1:
        graph[info].append(i)
        
answer = []
child_cnt = [0 for i in range(n)]

def dfs(x):
    global child_cnt
    childNode = []
    if len(graph[x]) == 0:
        child_cnt[x] = 0
    else:
        for child in graph[x]:
            dfs(child)
            childNode.append(child_cnt[child])

        childNode.sort(reverse=True)
        childNode = [childNode[i] + i + 1 for i in range(len(childNode))]
        child_cnt[x] = max(childNode)
        
dfs(0)
print(child_cnt[0])


1
3

트리가 주어졌을때, 모든 직원에게 정보를 전달하는데 걸리는 시간을 최소로 하려면 소식을 전하는 일을 위임 시켰을때, 전달하는데에 걸리는 시간이 오래걸리는 직원부터 전화를 해주어야한다. 따라서 가장 끝 노드부터 전파에 걸리는 시간을 차례 차례 조사한 뒤, 이 정보를 기반으로 전파에 걸리는 시간이 긴 직원부터 전화를 해주면 된다.

카테고리:

업데이트:

댓글남기기