[백준 1766번] 문제집 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappop,heappush

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

indegree = [0]*(N+1)
graph = {i:[] for i in range(1,N+1)}

for i in range(M):
  x,y = map(int,input().split())
  indegree[y] += 1
  graph[x].append(y)

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

while hq:
  now = heappop(hq)
  seq.append(now)
  for next in graph[now]:
    indegree[next] -= 1
    if indegree[next] == 0:
      heappush(hq,next)

print(" ".join(map(str,seq)))

 

위상정렬을 알면 아주 쉽게 풀 수 있는 문제.

위상정렬 알고리즘을 이용했던 줄세우기 문제와 코드가 거의 똑같지만 딱 하나, dq를 heapq로 바꿔주었다는 것만 다르다.

 

가능한 번호가 작은것부터 풀어야 하기 때문에 최소힙을 이용해준다.

 

간단한 문제였지만 이 문제의 풀이가 다른 문제에 활용하기 좋겠다는 생각도 했다. 이 문제에서는 난이도를 번호순이라고 해서 쉬웠지만, 이후에 어떤 순서로 배열하는 문제가 나왔을 때 이 문제에서의 개념을 활용할 수 있을 것이다.

 

 

오늘의 교훈) 위상정렬 + heapq를 잘 활용하자