[BOJ] 문제집

---

코드

import sys
import heapq
input = sys.stdin.readline

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

def topology_sort():
    result = []
    q = []
    for i in range(1, N+1):
        if indegree[i] == 0:
            heapq.heappush(q, i)

    while q:
        # 선수문제(indegree)가 없는 문제들 중 숫자가 작은 문제부터 푼다
        # 가장 작은 숫자를 빠르게 찾기 위해 우선순위큐를 사용한다
        v = heapq.heappop(q)
        result.append(v)
        # 바로 다음에 풀면 쉬운 문제를 풀고
        # 해당 문제는 선수문제를 푼 셈이므로 indegree를 하나 제거한다.
        for adj in graph[v]:
            indegree[adj] -= 1
            # 선수문제를 다 풀었다면 우선순위큐에 넣는다.
            if indegree[adj] == 0:
                heapq.heappush(q, adj)

    print(' '.join(map(str, result)))
    return

topology_sort()

결과

풀이 방법

• 위상정렬 + 우선순위큐
• 임의의 문제에 대해 먼저 풀어야 좋은 문제(a; 선수문제)의 개수를 진입차수로 보고 위상정렬을 수행하여 해결하는 문제이다.
• 선수문제가 없는 문제를 큐에 넣고 방문하되, 숫자가 작은 문제부터 푼다는 조건을 만족시켜야 하기 때문에 항상 큐에서 숫자가 가장 작은 문제를 꺼내야 한다.
• 따라서 위상정렬뿐만 아니라 우선순위큐(python에서는 heapq)를 사용하여 가장 작은 숫자를 빠르게 꺼내어 방문해야 한다.
• 선수문제가 없는 문제를 방문하여 풀었으면, 바로 다음에 풀면 좋은 문제(선수문제가 가리키는 노드)에서 진입차수를 하나 제거한다.
• 만약 남은 선수문제가 없다면 해당 문제는 풀어도 되므로 우선순위큐에 넣는다.

---