[알고리즘] 백준 1766번 : 문제집

백준 1766번 : 문제집 (문제 링크)

• 사용 언어 : 파이썬(Python)
• 문제 유형 : 힙, 위상정렬
• 난이도 : 중

소스코드

import sys, heapq

n, m = map(int, sys.stdin.readline().split())
array = [[] for i in range(n+1)]
indegree = [0] * (n+1)

heap = []
result = []

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    array[a].append(b)
    indegree[b] += 1

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

while heap:
    node = heapq.heappop(heap)
    result.append(node)
    if array[node]:
        for i in array[node]:
            indegree[i] -= 1
            if indegree[i] == 0:
                heapq.heappush(heap, i)

for i in result:
    print(i, end=' ')

설명

• 위상 정렬 알고리즘이란? : (링크)
• 이 문제는 전형적인 위상 정렬 알고리즘 문제이다.
• 문제의 3번 조건, 가능하면 쉬운 문제(즉, 번호가 작은)부터 풀어야 한다는 조건을 만족시키기 위해서는 일반 큐가 아닌 최소힙을 이용해야한다.
  

  

• 이 문제는 위상 정렬 + 최소힙을 이용해 해결할 수 있다.