[알고리즘] 백준2252 줄 세우기 - 파이썬

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

2252번: 줄 세우기

 

 

[풀이 코드] 

from sys import stdin
from collections import deque

input = stdin.readline

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

indegree = [0] * (n+1)
graph = [[] for i in range(n+1)]


for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def solution():
    result = []
    q = deque()

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

    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ')

solution()

- 위상 정렬은 큐를 이용하여 풀 수 있다. 이 문제에서 이상했던 점은 예제 입력 2의 출력 값이 '3 4 1 2'인데 정답처리가 된 것?? 아무래도 오타인 것 같다.. (???)