백준 #2252 #Python

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

이 문제는 우선순위가 정해져있기 때문에 순서를 정할 수 있는 위상정렬로 문제를 풀어야 합니다.

1. 위상정렬 문제를 풀기 위해선 각 노드마다 자식노드의 수를 기록합니다.
   자식 노드는 부모 노드보다 먼저 수행돼야 합니다.

2. 따라서, 자식 노드가 없는 노드(리프 노드)들이 가장 먼저 수행됩니다.
   수행된 노드들은 하나씩 지워줍니다.

3. 자식 노드가 모두 수행됐다면 해당 부모노드의 자식 노드 수는 0이 되고 리프노드가 되어 수행됩니다.

4. 2, 3번을 반복하며 모든 노드를 방문하면 됩니다.

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())

parentOf = [list() for _ in range(n+1)]
childs = [0]*(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    parentOf[b].append(a)
    childs[a] += 1         # 자식의 수를 기록

leaf = deque()
for i in range(1, n+1):
    if not childs[i]:      # 리프노드를 큐에 넣음
        leaf.append(i)

ans = []
while leaf:  
    now = leaf.popleft()
    for p in parentOf[now]:
        childs[p] -= 1     # 리프노드를 방문하며 해당 부모노드의 자식수를 1씩 줄임
        if not childs[p]:  # 자식이 없다면 부모노드를 큐에 넣음
            leaf.append(p)
    ans.append(str(now))

print(" ".join(ans[::-1]))