1. 문제 설명

트리

2. 문제 분석

리프 노드의 개수를 카운트하는 문제다. DFS 또는 BFS를 사용하자. 다음 노드를 방문할 수 없는 조건일 때 리프 노드임을 알 수 있다. 주어진 트리에서 루트 노드가 여러 개인 경우, 루트 노드가 잘린 경우 모두를 포함해야 한다는 점을 주의하자.

3. 나의 풀이

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
nodes = [[] for _ in range(n)]
# 트리를 방향 그래프로 구현
roots = []
for idx, tail in enumerate(list(map(int, sys.stdin.readline().rstrip().split()))):
    if tail == -1: roots.append(idx)
    # 해당 번호의 노드는 루트 노드
    else: nodes[tail].append(idx)
    # 자식 노드일 때에는 직전 부모 노드가 이 노드를 가리키도록 한다.

deleted = int(sys.stdin.readline().rstrip())
# 중간에서 끊어버린 노드
visited = [False for _ in range(n)]
visited[deleted] = True

queue = deque()
cnt = 0
# 리프 노드 개수 카운트

for root in roots:
    if not visited[root]:
        # 루트 노드가 끊기지 않았다면 큐에 넣고 시작
        queue.append(root)
        visited[root] = True
    while queue:
        cur_node = queue.popleft()

        is_leaf = True
        for next_node in nodes[cur_node]:
            if not visited[next_node]:
                is_leaf = False
                visited[next_node] = True
                queue.append(next_node)
        if is_leaf: cnt += 1
        # 리프 노드는 다음 노드를 방문할 수 없는 노드.

print(cnt)