https://www.acmicpc.net/problem/1068
-
문제
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.
현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.
이제 리프 노드의 개수는 1개이다. -
입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. -
출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
쉬워보였는데 오래걸려서 현타왔던 문제,,
우선 부모노드의 번호를 인덱스로 하는 리스트에 자식노드의 번호들을 원소들로 저장하고 이 리스트를 큐에 넣어서 사용하였다.
BFS방식으로 루트노드부터 리프노드까지 내려가며 탐색하였고 방문 체크를 해주었다.
우선, 생각하지 못한 예외사항 첫번째는 어느 노드가 하나의 자식노드를 가지고 있을 때 자식노드가 삭제된다면 그 부모노드가 리프노드라는 사실이다.
두번째는 루트노드가 0번이 아닐 수도 있다는 사실이다.
from collections import deque
N = int(input())
arr = list(map(int, input().split()))
del_n = int(input()) # 삭제 노드
cnt = 0 # 리프노드 개수
check = [0 for _ in range(N)] # 노드의 삭제여부
tree = deque([] for _ in range(N)) # 트리[부모] = 자식들
for i in range(N):
if arr[i] == -1: # 루트면
root = i
continue
else:
tree[arr[i]].append(i)
check[del_n] = 1 # 삭제체크
queue = deque() # dfs
queue.append(root) # 0에서 시작하게
while queue:
x = queue.popleft()
if check[x] == 1: # 삭제된 노드면
continue
if len(tree[x]) == 0: # 리프노드면(자식이 없으면)
cnt += 1
continue
n = len(tree[x])
while tree[x]: # 자식이 존재하면
y = tree[x].pop()
if n == 1 and check[y] == 1: # 자식이 하나있는데 그게 삭제된거면
cnt += 1
break
else:
queue.append(y) # 큐에 넣음
print(cnt)
# 리프노드인 경우 : 1. 자식이 없음 2. 삭제된 자식
# 주의 : 루트가 0이 아닐수도 있음 !