(Python) [BOJ 1068] 트리

(Python) [BOJ 1068] 트리

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

주어진 트리에서 삭제하고자 하는 노드를 지웠을 때의 리프 노드의 총개수를 계산해서 출력해야 하는 문제입니다.

노드를 삭제하는 행위를 DFS의 탐색에서 제외하는 것으로 해석하여 코드를 작성하였습니다. 즉, 특정 노드를 삭제한 후의 트리를 대상으로 DFS를 돌린 것이 아니라 애초에 DFS를 돌릴 때 삭제 대상 노드를 발견하면 해당 경로로는 DFS 탐색을 진행하지 않도록 조정하였습니다.

여기서 한 가지 주의할 점은 삭제 대상 노드를 발견했을 때, 만약 해당 노드가 유일한 자식이라면 리프 노드의 개수에 포함시켜줘야 한다는 것입니다.

import sys def count_leaves(node_idx): # DFS global ans if TARGET == node_idx: # 혹시 루트 노드 단 하나로 구성된 트리가 있을까봐 return if not graph[node_idx]: # 자식이 없다면 즉, 리프 노드이면, ans += 1 # 카운트 return for node_nex in graph[node_idx]: if TARGET == node_nex: # 다음 노드가 지우고자 하는 타겟 노드이면, if len(graph[node_idx]) == 1: # 자식 노드가 이 타겟 노드 하나 뿐이라면, ans += 1 # 카운트하고 건너 뛰기(지우기) continue else: # 그렇지 않다면, 그냥 건너 뛰기(지우기) continue count_leaves(node_nex) # 1. INPUT & SETTING N = int(sys.stdin.readline()) graph = [[] for _ in range(N)] # 인접 리스트 root = -1 # 루트 노드의 인덱스를 저장할 변수 PARENT = list(map(int, sys.stdin.readline().split())) for node_idx in range(N): if PARENT[node_idx] == -1: root = node_idx continue graph[PARENT[node_idx]].append(node_idx) TARGET = int(sys.stdin.readline()) # 2. BODY ans = 0 # 카운트 결과를 저장할 변수 count_leaves(root) # 리프 노드 카운트 하기: 루트 노드의 인덱스 # 3. OUTPUT print(ans)

from http://sangdanghyunjeo.tistory.com/7 by ccl(A) rewrite - 2021-12-14 15:00:21