[백준] 2252번 줄 세우기 파이썬 코드

코드

# 키순서는 사이클이 생길 수 없다.
# 따라서 유향 비순환 그래프라고 할 수 있다
# 정렬을 해주어야 하므로 위상정렬을 사용하면 된다.

import sys
from collections import deque
input = sys.stdin.readline

def topol_sort():
  queue = deque()
  for i in range(1,n+1):
    if indegree[i] ==0: # 전입차수가 0인 값을 큐에 삽입
      queue.append(i)
  while queue:
    popnum = queue.popleft()
    for j in graph[popnum]:
      indegree[j] -= 1 # 전입차수 하나 삭제
      if indegree[j] == 0: # 전입차수가 0인 값을 큐에 삽입
        queue.append(j)
    print(popnum, end= ' ') # 위상정렬로 정렬된 값이 순서대로 출력된다

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
indegree = [0]*(n+1) #전입차수 전출차수 기록용
for _ in range(m):
  x,y = map(int, input().split())
  graph[x].append(y)
  indegree[y]+=1 # 전입차수 1 증가
topol_sort()

위상정렬을 그대로 적용하면 되는 문제.