[백준] 1068번 트리 - 파이썬/DFS

https://www.acmicpc.net/problem/1068

N = int(input())

graph = [ [] for _ in range(N) ]
visited = [0]*N

N_list = list(map(int,input().split()))

for i in range(len(N_list)):

    if N_list[i] != -1:
        graph[N_list[i]].append(i)

# print(graph)

D = int(input())


def dfs(D):

    visited[D]=True

    for i in graph[D]:
        if not visited[i]:
            dfs(i)

dfs(D)

# print(visited)
cnt = 0
for i in range(len(graph)):
    if visited[i] == 0 and (len(graph[i]) == 0 or [D] == graph[i]):
        cnt+=1

print(cnt)

주요 반례로는

이런 식으로 제거했을때 2번 노드가 루트노트가 되는 경우가 있었다.

그래서 인접그래프가 지우는 노드 그 자체인 경우의 조건을 추가해주었다.