[알고리즘] 백준 1135 - 뉴스 전하기

1. 문제

뉴스 전하기

2. 접근

* 본인이 한번에 문제를 이해도 못하고 못풀어서 다른 사람의 풀이를 참고해서 풀었습니다

 

1. 트리에 대한 구조를 만든다 ( 비워져 있는 2차원 배열 )

2. 트리에 입력받은 데이터들을 0 ~ n-1 인덱스에 1 ~ n 까지의 정보들을 넣어준다

3. go 함수 안에서 먼저 leaf 노드까지 쭉내려가서 leaf node에서의 시간을 0이라고 지정해주기

4. 다음 자식 노드가 있다면, 자식 노드에 대해서도 leaf까지 내려가게 함수 재사용하기

5. 자식 노드까지의 걸리는 시간을 새로운 리스트(child_node) 안에 넣어준다

6. 새롭게 만든 리스트를 내림차순으로 정리하고 현재까지 걸린 시간 + 현재 처리시간을 넣고 최대값을 뽑아 출력한다

 

3. 풀이

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))
tree = [[] for _ in range(n)]
time_to_child = [0] * n

for i in range(1, len(data)):
    tree[data[i]].append(i)


def go(x):
    global child_cnt
    child_node = []

    if len(tree[x]) == 0:
        time_to_child[x] = 0

    else:
        for child in tree[x]:
            go(child)
            child_node.append(time_to_child[child])
        child_node.sort(reverse=True)
        child_node = [child_node[i] + i + 1 for i in range(len(child_node))]
        time_to_child[x] = max(child_node)


go(0)
print(time_to_child[0])