[Baekjoon] DFS - 1068 트리

문제

1068번: 트리

 

풀이

1. root node는 여러 개일 수 있다.

2. 제거할 node는 연결 그래프를 만들지 않는다.

3. 제거할 node이거나 이미 방문한 경우라면 탐색을 종료한다.

4. Leaf Node인 경우 탐색을 종료하고 Count한다.

 

import sys

n = int(sys.stdin.readline().rstrip())
nodes = [[] for _ in range(n)]
parent = list(map(int, sys.stdin.readline().rstrip().split()))
m = int(sys.stdin.readline().rstrip())

visited = [False] * n
visited[m] = True

roots = []

for index, value in enumerate(parent):
    # 제거할 노드이므로 애초부터 넣지 않음
    if index == m:
        continue

    if value == -1:
        roots.append(index)
        continue
    nodes[value].append(index)


def dfs(graph, start, visited, result):
    # 이미 방문한 경우라면(or 삭제 처리된 경우라면) 더 이상 탐색하지 않고 종료
    if visited[start]:
        return

    # Leaf Node인 경우 종료
    if not len(graph[start]):
        result.append(True)
        return

    visited[start] = True

    for v in graph[start]:
        if not visited[v]:
            dfs(graph, v, visited, result)

result = []

for root in roots:
    dfs(nodes, root, visited, result)

print(len(result))

 

채점 결과