[Python] 백준 1766 문제집

1766번: 문제집

위상정렬 : 위상정렬에 우선순위 큐를 사용해야 한다. 파이썬은 힙큐가 있기 때문에 너무 쉽다. 하지만 좀 막막할 수가 있다. 힙큐 쓰는 것을 솔직히 알고리즘 분류 클릭해보고 나서 알았다. 

 

전체코드

import sys
import heapq
import collections

input = sys.stdin.readline

N, M = map(int, input().split())
inDegree = [0 for _ in range(N + 1)]

graph = collections.defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    inDegree[B] += 1

heap = []
for i in range(1, N + 1):
    if inDegree[i] == 0:
        heapq.heappush(heap, i)

result = []
while heap:
    node = heapq.heappop(heap)
    result.append(node)
    for i in graph[node]:
        inDegree[i] -= 1
        if inDegree[i] == 0:
            heapq.heappush(heap, i)
print(*result)