[Python] 백준 1135번: 뉴스 전하기

 

1135번: 뉴스 전하기 (acmicpc.net)

1135번: 뉴스 전하기

1. 자식 노드들의 자식이 많을수록 전화를 빨리 걸어야 한다. 

2. 자식 노드들의 자식들을 배열에 넣어 자식이 많은순으로 정렬한다.

3. 제일 높은값이 정답이다.

n = int(input())
emp = list(map(int, input().split()))
node = [[] for _ in range(n)]
child_cnt = [0 for _ in range(n)]


def go(x):
    global child_cnt
    child_node = []
    if len(node[x]) == 0:
        child_cnt[x] = 0
    else:
        for child in node[x]:
            go(child)
            child_node.append(child_cnt[child])

        child_node.sort(reverse=True)
        child_node = [child_node[i] + i + 1 for i in range(len(child_node))]
        child_cnt[x] = max(child_node)


for i in range(1, len(emp)):
    node[emp[i]].append(i)

go(0)
print(child_cnt[0])