[BOJ] 1135 뉴스전하기 (Python3)
문제
민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.
민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 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
트리가 주어졌을때, 모든 직원에게 정보를 전달하는데 걸리는 시간을 최소로 하려면 소식을 전하는 일을 위임 시켰을때, 전달하는데에 걸리는 시간이 오래걸리는 직원부터 전화를 해주어야한다. 따라서 가장 끝 노드부터 전파에 걸리는 시간을 차례 차례 조사한 뒤, 이 정보를 기반으로 전파에 걸리는 시간이 긴 직원부터 전화를 해주면 된다.
댓글남기기