백준_python 1068번 트리 (DFS)

<문제 링크>

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

 

 

<정답 코드>

 sol ) dfs를 이용한 리프 노드 탐색

import sys
input = sys.stdin.readline
 
def dfs(node, tree, visited):
    visited[node] = True
    for i in range(len(tree)):
        if tree[i] == node and not visited[i]:
            dfs(i, tree, visited)
 
n = int(input())
tree = list(map(int, input().split()))
del_node = int(input())
 
visited = [False] * n
 
# 삭제할 노드와 그 자손들 방문 처리
dfs(del_node, tree, visited)
 
# 리프 노드 계산
leaf_cnt = 0
for i in range(n):
    if not visited[i]:
        # 현재 노드가 리프 노드라고 일단 가정
        is_leaf = True
        for j in range(n):
            # 노드 j의 부모 노드가 i이고 삭제되지 않은 경우(not visited[j])
            if tree[j] == i and not visited[j]:
                # i는 리프노드가 아님
                is_leaf = False
                break
        if is_leaf:
                leaf_cnt += 1
 
print(leaf_cnt)

 

 

DFS로 삭제 대상 노드의 자식 노드들을 모두 방문하고

방문하지 않은 노드 대상으로 리프 노드 여부를 검사해 그 수를 센다.

 

DFS가 그래프 전체 뿐만 아니라 부분에 대한 탐색을 할 때도 사용할 수 있다는 아이디어를 떠올리지 못했다.