[BOJ] 1766번 : 문제집(위상정렬, 우선순위 큐)

접근

이름에서부터 뿜어져 나오는 위상정렬의 향기. 위상정렬에 대한 해설은 이전 게시글을 참고하자.

2023.12.20 - [알고리즘(Algorithm)] - [BOJ] 1005번 : ACM Craft(위상 정렬, dp)

 

문제 풀이의 우선순위 조건이 몇가지가 있다.

• 문제 번호가 더 큰 문제가 어려운 문제
• 먼저 푸는 것이 좋은 문제가 있다면, 그 문제부터 해결해야함
• 쉬운 문제부터 풀기

문제풀이의 우선순위(선수과목)이 있다면, 웬만하면 위상정렬일거라 생각해서 위상정렬로 방향을 잡았다.

 

해결

위상정렬로 기본적인 알고리즘을 구현하되, "쉬운 문제부터 풀기" 이 조건을 해결하기 위해 우선순위 큐를 사용했다.(나는 Heap큐를 사용했다)

코드가 간단하니 해설은 길게하지 않겠다. 위의 위상정렬해설과 아래 코드를 같이 보면, 어렵지 않은 문제라고 예상한다.

 

코드

import sys
import heapq

from collections import defaultdict

input = sys.stdin.readline

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

graphs = defaultdict(list)
orders = defaultdict(int)
for _ in range(M):
    a, b = map(int, input().split())
    graphs[a].append(b)
    orders[b] += 1

que = []
for i in range(1, N+1):
    if not orders[i]:
        heapq.heappush(que, i)

while que:
    v = heapq.heappop(que)
    
    print(v, end=" ")
    for nv in graphs[v]:
        orders[nv] -= 1
    
        if orders[nv] == 0:
            heapq.heappush(que, nv)