[알고리즘][Python] 백준(BOJ) 1068 트리_파이썬

 

1068 트리    www.acmicpc.net/problem/1068

1068번: 트리

 

 

 

 

 

문제 풀기 전 공부할 것 : 그래프, 트리, 깊이 우선 탐색

 

 

 

 

 

 

 

 

풀이

<내용>

• 각 노드의 부모를 parents에 저장한다.
• 삭제할 노드도 del_node에 저장하고 tree 맵을 만든다.
• parents를 for문으로 돌면서 삭제할 노드이거나 삭제할 노드를 부모로 둔 노드를 제외하고 tree에 저장한다.
• 삭제한 노드가 루트라면 빈 리스트를, 아니라면 [-1]를 que에 저장한다.
• tree를 돌면서 리프 노드의 개수를 센다.

 

 

 

<코드>

n = int(input())
parents = list(map(int, input().split()))
del_node = int(input())
tree = {}
for i in range(n):
    if i == del_node or parents[i] == del_node:
        continue
    if parents[i] in tree:
        tree[parents[i]].append(i)
    else:
        tree[parents[i]] = [i]
        
res = 0
if -1 in tree:
    que = [-1]
else:
    que = []
while que:
    node = que.pop()
    if node not in tree:
        res += 1
    else:
        que += tree[node]
print(res)