[백준] 1068번 - 트리

---

문제 분석

트리의 관계를 인접리스트로 표현하고, DFS를 통해 부모-자식의 관계를 설정하여 표현할 수 있다.
따라서 DFS 및 visited배열을 통해 주어진 입력대로 관계를 설정하고 풀어나가면 된다.

---

소스 코드

# 트리

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

N = int(input())
numList = list(map(int, input().split()))
deleteNode = int(input())
arr = [[] for _ in range(N)]
visited = [False] * N
rootNode = 0
leafCnt = 0

for i in range(N):
    if numList[i] == -1:
        rootNode = i
    else:
        arr[i].append(numList[i])
        arr[numList[i]].append(i)


def DFS(idx):
    global leafCnt
    visited[idx] = True
    isLeaf = True
    for v in arr[idx]:
        if not visited[v] and v != deleteNode:
            isLeaf = False
            DFS(v)
    if isLeaf:
        leafCnt += 1


if rootNode == deleteNode:
    print(0)
else:
    DFS(rootNode)
    print(leafCnt)