BOJ 2252 줄 세우기

문제

접근 방법

문제에서 정해준 순서를 바탕으로 전체 순서를 구하는 문제이다. Graph에서 순서를 엮은 문제는 Topological sort이 최적의 풀이라고 생각했다. 중복이 된다면 아무렇게나 하라고 했으므로 그냥 queue에서 나오는 순서대로 result에 다 넣었다.

정답 코드

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

'''
키 작은 애를 edge의 시작, 큰 애를 edge의 끝으로 설정

topological sort을 하면 될 듯
'''

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

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

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


def topological_sort():
  nexts = deque()
  result = []

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

  while nexts:
    node = nexts.popleft()
    result.append(node)
    for next in graph[node]:
      if inorder[next]>0:
        inorder[next]-=1
        if inorder[next]==0:
          nexts.append(next)
  return result


result = topological_sort()
print(*result)