백준 21276 [계보 복원가 호석] 파이썬

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

 

#백준 21276 계보 복원가 호석
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

names = ['_'] + list(map(str, input().split()))
names.sort()

ancestor_to_child = [[] for _ in range(N+1)]  # 부모 → 자식 목록
in_degree = [0] * (N+1)                       # 부모 수(진입 차수)
childs = [[] for _ in range(N+1)]             # 직계 자식 목록
ancestor_of_ancestor = []                     # 최상위 조상 목록

name_to_num = {}
num_to_name = {}
for i in range(1, N+1):
    name_to_num[names[i]] = i
    num_to_name[i] = names[i]

M = int(input())

# A: 자식, B: 부모
for _ in range(M):
    A_name, B_name = map(str, input().split())
    A_num = name_to_num[A_name]
    B_num = name_to_num[B_name]
    ancestor_to_child[B_num].append(A_num)  # 부모 → 자식
    in_degree[A_num] += 1                   # 자식의 부모 수 증가

q = deque()

# 부모가 없는 사람(진입 차수 0)이 최상위 조상
for i in range(1, N+1):
    if in_degree[i] == 0:
        ancestor_of_ancestor.append(i)
        q.append(i)

# 위상정렬
while q:
    ancestor_ = q.popleft()
    for child_ in ancestor_to_child[ancestor_]:
        in_degree[child_] -= 1
        if in_degree[child_] == 0:  # 모든 부모 처리 완료 → 직계 자식 확정
            childs[ancestor_].append(child_)
            q.append(child_)

# 출력
print(len(ancestor_of_ancestor))
for anc in ancestor_of_ancestor:
    print(num_to_name[anc], end=' ')
print()

for i in range(1, N+1):
    childs[i].sort()
    print(num_to_name[i], end=' ')
    print(len(childs[i]), end=' ')
    for c in childs[i]:
        print(num_to_name[c], end=' ')
    print()

겨우 풀었다.

핵심은 자식-> 부모로 트리를 생성하는것이 아닌, 부모-> 자식으로 가는 트리를 생성하는 것이다!

그 후, BFS 위상정렬(Khan's Algorithm) 이용하여 해결하였다.