백준 1766번 : 문제집 in Python

1766번: 문제집

 

www.acmicpc.net

이 문제는 문제집을 풀 때 문제를 푸는 순서를 정하는 문제이다. 문제를 풀 때 먼저 푸는 것이 좋은 문제가 있는 문제는 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 하고, 가능하면 쉬운 문제부터 풀어야 한다는 조건이 있다. 즉, 우선 순위 면에서 선행 문제를 먼저 푸는 것이 쉬운 문제를 푸는 것보다 더 중요하다.

이는 각 문제를 그래프의 정점에, 선행 문제를 먼저 푸는 문제는 그래프 내의 간선에 대응시킨 뒤 위상 정렬을 하는 방식으로 문제를 해결한다. 예를 들어 4번 문제를 먼저 푼 뒤 2번 문제를 풀어야 하면 간선 (4, 2)를 그래프에 추가한다.

위상 정렬을 할 때 가능한 쉬운 문제부터 풀어야 하므로 기존의 위상 정렬에서 사용한 queue 대신 매번 배열에서 정점을 뽑을 때 가장 작은 정점을 뽑을 수 있게 min heap을 사용한다. 

이를 제외한 나머지 부분은 기존의 위상 정렬 문제에서 사용한 코드와 같다.

이를 코드로 구현하면 다음과 같다.

import heapq
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
deg = [0 for _ in range(N+1)]
# 위상 정렬에서 사용한 queue 대신 minheap을 사용한다.
heap = []
res = []
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    deg[B] += 1
for i in range(1, N+1):
    if deg[i] == 0:
        heapq.heappush(heap,i)
while heap:
    u = heapq.heappop(heap)
    res.append(u)
    for v in graph[u]:
        deg[v] -= 1
        if deg[v] == 0:
            heapq.heappush(heap,v)
print(" ".join(list(map(str, res))))