백준 1068번: 트리

백준 1068번: 트리

from collections import deque
N=int(input())
parent = list(map(int,input().split()))
nodes=[[] for _ in range(N)]
num = int(input())
visit = [0 for _ in range(N)]
for idx in range(N):
    if parent[idx]!=-1:
        nodes[parent[idx]].append(idx)
queue = deque()
queue.append(num)
visit[num]=1
while queue:
    x = queue.popleft()
    for i in nodes[x]:
        if visit[i]==0:
            queue.append(i)
            visit[i]=1

def check_leaf_node(idx):
    for i in nodes[idx]:
        if visit[i]==0:
            return False
    return True
res = 0
for idx in range(N):
    if check_leaf_node(idx) and (visit[idx]==0):
        res+=1
print(res)

골드 문제치고는 조금 쉬웠던 느낌?! 처음에는 마지막 리프노드 체크 로직에서 len(nodes[idx])==0으로 했는데 70%대에서 틀렸다. 그래서 반례 찾아보고 고민해보니 자식 노드가 하나인데 그 자식 노드가 삭제하는 노드인 경우처럼 nodes[idx]는 0이 아니지만 노드가 삭제돼서 실질적인 노드값은 0이 되는 경우가 있어서 check_leaf_node() 함수를 만들어서 리프노드 여부를 체크해줬다. 문제를 풀면서 반례를 고민해보는 게 제일 중요한 것 같다.