[백준] 1766번 문제집 파이썬 코드

코드

# 선수문제, 위상정렬로 하되 큐에 들어가는 값에 우선순위가 있다.
# 큐를 이용할 때 우선순위가 생기면 우선순위 큐를 사용한다.
# 여기서는 앞에 문제가 뒤에 문제보다 쉽기 때문에 우선순위 큐를 사용해준다. 

import sys, heapq
input = sys.stdin.readline

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

def topol_sort():
  solve = []
  queue = []
  for i in range(1, n+1):
    if indegree[i] == 0:
      heapq.heappush(queue,i)
  while queue:
    popnum = heapq.heappop(queue)
    solve.append(popnum)
    for j in graph[popnum]:
      indegree[j] -= 1
      if indegree[j] == 0:
        heapq.heappush(queue,j)
  return solve
ps = topol_sort()
print(*ps)

우선순위 큐를 사용하지 않고 임의로 sort를 했다가 틀린 문제. 우선순위 큐가 있다는 사실을 망각하고 있었다. 이번을 계기로 기억해두자