백준 2252번 python 풀이 - 줄세우기

문제 링크

2252번

해결책

import sys


N, M = map(int, sys.stdin.readline().rstrip().split())

indegree =[0 for i in range(N+1)]

paths = [[] for i in range(N+1)]

for i in range(M):
    _from, _to = map(int, sys.stdin.readline().rstrip().split())
    indegree[_to] += 1
    paths[_from].append(_to)

que = []
ans = []
for i in range(1, len(indegree)):
    if indegree[i] == 0:
        que.append(i)

while que:
    cur = que.pop(0)
    ans.append(cur)
    print(cur, end=" ")
    for _to in paths[cur]:
        indegree[_to] -= 1
        if (indegree[_to] == 0) and (_to not in ans):
            que.append(_to)
    paths[cur] = []

주석으로 달 설명

위장 정렬. Topology Sort를 이용한 풀이이다.