BOJ 1766 문제집

문제

접근 방법

일반적인 topological sort 문제라고 볼 수 있다. 하지만 조건 3: 가능하면 쉬운 문제부터 풀어야 한다. 과 1번 문제가 제일 쉽고 N번 문제가 제일 어렵다는 조건에서 topological sort로만 풀 수 없음을 알 수 있다. 이 조건들을 만족하기 위해서는 다음 순서로 올 수 있는 것들 중에서 제일 숫자가 작은 문제를 pop 할 수 있어야 한다. 따로 계속 정렬하기에는 시간 제한 때문에 어렵다. queue 내에서 알아서 정렬이 되어야 한다는 것을 알 수 있다.

$\rightarrow$ 여기서 heapq, 우선순위 큐를 사용해야 함을 알 수 있어야 한다.

정답 코드

import sys
import heapq
input = sys.stdin.readline

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():
  result = []
  q = []

  for i in range(1,n+1):
    if inorder[i]==0:
      heapq.heappush(q, i)

  while q:
    cur = heapq.heappop(q)
    result.append(cur)
    for next in graph[cur]:
      if inorder[next]>0:
        inorder[next]-=1
        if inorder[next] == 0:
          heapq.heappush(q, next)
  print(*result)

topological_sort()