문제 링크

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

문제 설명

• 트리가 주어짐
• 노드 하나를 삭제했을 때 리프 노드의 개수 출력

풀이

• 입력이 부모 리스트로 주어져서
• 인접 리스트를 만들어주고
• BFS를 사용했다

코드

import sys
from collections import deque

def solution():
    read = sys.stdin.readline
    n = int(read())
    parents = list(map(int, read().split()))
    to_delete = int(read())

    # 루트를 삭제하면
    if parents[to_delete] == -1:
        print(0)
        return

    root = -1
    adj_list = [[] for _ in range(n)]
    for child in range(n):
        if child == to_delete:
            continue
        parent = parents[child]
        if parent == -1:
            root = child
            continue
        adj_list[parent].append(child)

    print(bfs(root, adj_list))

def bfs(root, adj_list):
    count = 0
    q = deque([root])
    while q:
        parent = q.popleft()
        if not adj_list[parent]:
            count +=1
        for child in adj_list[parent]:
            q.append(child)
    return count

solution()