[Python Algorithm] 백준 문제집 - 1766

풀이 과정

위상정렬을 사용해서 푸는 문제이다.
주의해야 할 점은 각 노드에서 우선순위가 있기 때문에 일반 큐가 아닌 우선순위 큐를 사용하여 구현해야한다.
우선순위 큐를 사용한다는 아이디어만 생각해내면 정말 편하게 풀 수 있는 문제 !

최종 코드

from heapq import heappop, heappush

N, M = map(int, input().split(' '))

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

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

q = []

for i in range(1, N + 1):
  if indegree[i] == 0:
    heappush(q, i)

while q:
  problem = heappop(q)

  print(problem, end=' ')

  for p in graph[problem]:
    indegree[p] -= 1
    if indegree[p] == 0:
      heappush(q, p)

결과

Link

문제집 문제 출처
GitHub 코드