백준 1068 트리

문제 바로가기
골드 V (22.11.15 기준)

✏ 생각하기

문제에서 구하는 것은 리프 노드의 개수다.
트리에서 리프 노드란, 자손의 개수가 0인 노드를 말한다. 입력으로 노드 개수 N과 각 노드의 부모노드(루트일 경우 -1), 그리고 지울 노드가 주어진다. 지워진 노드는 물론 지워진 노드의 모든 자손 노드들이 트리에서 제거된다.
따라서 루트노드에서 그래프 탐색을 시작하여, 자식 노드가 없는 노드를 찾을 경우 결과값 cnt 를 1씩 증가시키면 될 것이다. 단 제거된 노드가 있음을 주의해야 한다.

📒 알고리즘

부자 관계가 중요하므로 DFS로 탐색한다. BFS도 가능하나 풀이의 직관성이 떨어진다.
1. 입력값으로부터 각 노드에 자식 노드들을 저장한 리스트를 생성한다. 이러면 루트 노드부터 탐색하기 편해진다. 단, 자식 노드나 부모 노드가 제거 노드일 경우 제외한다.
2. DFS를 수행, 자식 노드가 없을 경우 cnt += 1 한다.

💻 코드

import sys

n = int(sys.stdin.readline())
parents = list(map(int, sys.stdin.readline().split()))
remove = int(sys.stdin.readline())
tree = [[] for _ in range(n)]
root = -1
for i in range(n): 
    if i != remove and parents[i] != remove:  # 제거할 노드 고려
        if parents[i] == -1: 
            root = i
        else: 
            tree[parents[i]].append(i)

cnt = 0
def dfs(n1): 
    global cnt
    for n2 in tree[n1]: 
        dfs(n2)
    if len(tree[n1]) == 0: 
        cnt += 1

if root != -1: 
    dfs(root)
print(cnt)