[BOJ] 1068 - 트리 (Python)

 

 

아이디어

 

노드를 지운 후 BFS로 자식이 없는 리프 노드의 개수를 센다.

 

 

풀이

 

2차원 리스트 tree에 지울 노드를 제외한 나머지 자식 노드의 번호를 자신의 부모 노드 인덱스에 맞춰 추가한다.

BFS로 자식이 없는 리프 노드의 개수를 세어 결과값으로 출력한다.

지울 노드는 tree에 추가하지 않았으므로 탐색하지 않고 BFS가 종료된다.

 

N = int(input())
tree = [[] for _ in range(N)]
P = map(int, input().split())
r = int(input())
li = []
for idx, n in enumerate(P):
    if idx != r:
        if n >= 0:
            tree[n].append(idx)
        else:
            li.append(idx)
res = 0
while li:
    idx = li.pop()
    if not tree[idx]:
        res += 1
    for i in tree[idx]:
        li.append(i)
print(res)