[백준 21276번] 계보 복원가 호석 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
name = sorted(input().split())

M = int(input())

child = {i:set() for i in name}
realchild = {i:set() for i in name}
indegree = {i:0 for i in name}
for i in range(M):
  c,p = input().split()
  child[p].add(c)
  indegree[c] += 1

father = []
dq = deque()
for i in name:        #시조
  if not indegree[i]:
    father.append(i)
    dq.append(i)

while dq:
  now = dq.popleft()
  for next in child[now]:
    indegree[next] -= 1
    if indegree[next]:
      continue
    dq.append(next)
    realchild[now].add(next)

print(len(father))
print(" ".join(father))
for i in name:
  print(i,end=" ")
  print(len(realchild[i]),end=" ")
  for c in sorted(realchild[i]):
    print(c,end=" ")
  print()

 

문제 설명이 약간 난해하게 되어있었는데 결국 전형적인 위상정렬 문제이다.

 

요약하면,

1. 각 사람들에 대해서 각각의 자손들을 child list에 넣어주고, 자손들은 indegree를 1씩 늘린다.

2. indegree가 0인 사람이 곧 시조이며, father list에 넣어준다.

3. BFS로 위상정렬을 하는 과정에서 각 자식들의 indegree를 1 뺐을때 0이 되는 경우 realchild에 추가한다.

4. father와 모든 사람들에 대한 realchild를 출력한다.

 

 

오늘의 교훈) 위상정렬은 매우 편리하다.