[ baekjoon ] 줄 세우기 2252번 ( python )

문제

백준 2252 줄 세우기 풀이 ( 파이썬 )

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

2252번: 줄 세우기

 

풀이

뭔가 쉬워보이듯 어떻게 해야하나 했는데 순서라는 말이 나왔을 때 위상정렬을 생각하면 되는 것 같다.

단순히 위상정렬을 적용하니 풀렸다.

from collections import deque
import sys

input=sys.stdin.readline

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

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

visited=[0]*(n+1)



for i in range(m):
    st,ed=map(int,input().split())
    graph[st].append(ed)
    indegree[ed]+=1

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

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

print(*ans)