![[1068] 트리 (리프 노드의 개수 구하기, DFS)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbgOptD%2Fbtsiu1tVi8d%2FIwQn8NTWFlpDczyL16Ekxk%2Fimg.png)
728x90
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
n=int(input())
parent=list(map(int, input().split()))
deleteNode=int(input())
tree = [[] for _ in range(n)]
root=0
for i in range(n):
if parent[i]!=-1:
tree[parent[i]].append(i)
tree[i].append(parent[i])
else:
root=i
visited = [False]*(n+1)
cnt=0
def dfs(v):
global cnt
visited[v] = True
cNode=0
for i in tree[v]:
if not visited[i] and i!=deleteNode:
cNode+=1
dfs(i)
if cNode==0:
cnt+=1
if deleteNode==root:
print(0)
else:
dfs(root)
print(cnt)
728x90