백준 1068 트리

골드5 난이도의 트리 문제 인데 정답률이 낮아 도전해보았다.

📜 문제 바로 가기 : 트리

제출코드

import sys
input = sys.stdin.readline

from collections import deque

N = int(input())
parent = list(map(int, input().split())) # i 노드의 부모노드
M = int(input()) # 삭제할 노드

child = [[] for _ in range(N)] # i 노드의 자식 노드들

rootNode = -1
for i in range(N):
   p = parent[i] # p = i 노드의 부모노드
   if p == -1:
       rootNode = i
   elif i != M:
       child[p].append(i)


ans = 0 # 리프노드 개수
que = deque()
if M != rootNode:
   que.append(rootNode)
while que:
   node = que.popleft()
   if len(child[node]) == 0:
       ans += 1
   for i in child[node]:
       que.append(i)


print(ans)

---

접근 방법

루트 노드부터 BFS 형태로 자식노드로 가는 방법을 선택했다. 그래서 주어진 부모노드 관계 정보로 자식 노드 배열을 만들어 줬다 child . 이 때 삭제한 노드는 빼고 등록해줌으로써 관계를 끝었다. 자식노드 배열을 만들때 자연스럽게 parent 배열을 완전탐색 함으로 겸사겸사 루트노드 또한 이때 찾아 줬다.

그 후 BFS 형태로 코드를 썼는데 나는 자식 노드가 없는 경우를 리프노드 로 판단하게끔 해서 계산했다.

주의할점이 있다면 루트 노드 자체를 제거하는 경우를 고려해야 한다는 점 정도가 있겠다.