BOJ 2252 줄 세우기 - Python

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

가장 기본적인 위상정렬을 통해 해결 할 수 있다.
어떤 사람 뒤에 어떤 사람이 와야하는지를 정렬하는 것이기 때문이다.

from collections import deque

N, M = map(int, input().split())
arr = [[] for i in range(N + 1)]
indegree = [0 for _ in range(N + 1)]

for i in range(M):
    first, second = map(int, input().split())
    arr[first].append(second)
    indegree[second] += 1

queue = deque()

for i in range(1, N + 1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    temp = queue.popleft()
    print(temp, end = " ") # indegree가 0이 된 순서 대로 print를 해준다. 
    for second in arr[temp]:
        indegree[second] -= 1 # indegree를 줄여주고
        if indegree[second] == 0: # 0일 때는 자기 보다 앞에 사람이 다 세워졌다는 소리이므로 queue에 넣어준다.
            queue.append(second)