백준 1068 : 트리 (Python)

본문 링크

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

N=int(input())
Tree=list(map(int,input().split()))
Find=int(input())

def DFS(Find,Tree):

    Tree[Find]=-2
    for i in range(len(Tree)):
        if Find==Tree[i]: 
            DFS(i,Tree)

DFS(Find,Tree)
count=0
for i in range(len(Tree)):
    if Tree[i]!=-2 and i not in Tree:
        count+=1
print(count)

📌 어떻게 접근할 것인가?

트리가 주어졌을때 임의의 노드를 삭제시킨후에 리프노드의 개수를 구하는 문제이다.

간단하게 삭제하고자 하는 노드와 그 하위 노드들을 전부다 -2 로 처리해준다.

이후 트리의 크기를 전부 탐색하면서 삭제되지 않으면서 부모가 없는 , 리프노드인 값들의 개수를 출력해준다.