[백준] 1068 트리 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1068
• DFS
• 부모 노드를 지우면 자식 노드로 갈 길이 없어지기 때문에
• 제거해야 할 노드만 지우면 자식 노드들을 다 지울 필요 없다.

 

import sys
from collections import defaultdict
input = sys.stdin.readline

tree = defaultdict(list)

n = int(input())
nodes = list(map(int, input().split()))
remove_node = int(input())

for i in range(n):
    if i != remove_node:    # 제거해야 할 노드 제외하고 추가
        tree[nodes[i]].append(i)

if remove_node in tree: # 제거해야 할 노드가 value값이 아닌 key값으로 있는 경우 제거
    tree.pop(remove_node)

answer = 0

def dfs(d):
    global answer

    for i in tree[d]:
        if tree[i] == []:   # 더 이상 갈 곳이 없는 리프 노드일 때
            answer += 1
        dfs(i)
        
dfs(-1) # 루트부터 시작

print(answer)