[백준] 1766번: 문제집

문제

백준 - 1766번: 문제집

분석

난이도 순서인 N개의 문제가 있고, '먼저 푸는 것이 좋은 문제'가 있다고 할 때 다음 세 가지 조건에 따라 문제를 풀 순서를 정하는 프로그램을 작성하는 문제이다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

다른 위상정렬 문제와 똑같이 푸는데, 낮은 숫자가 먼저 오는 조건이 있기 때문에 답이 하나로 정해진다.

일반적인 위상정렬 문제에서 그냥 큐를 사용했다면, heapq를 사용해서 가장 작은 수를 항상 앞에 오게 하면 위의 조건을 해결할 수 있다.
또한, 문제에서 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다고 했으므로 heapq에 아무것도 없을 때 pop하는 경우는 없다. (예외처리가 필요 없다.)

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from heapq import heappush, heappop
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
degree = [0]*(n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    degree[b] += 1

pq = []
for i in range(1, n+1):
    if degree[i] == 0:
        heappush(pq, i)

result = []
for _ in range(1, n+1):
    x = heappop(pq)
    result.append(x)
    while graph[x]:
        y = graph[x].pop()
        degree[y] -= 1
        if degree[y] == 0:
            heappush(pq, y)

print(*result)

끝으로..

기본적인 알고리즘에 하나씩 다른 알고리즘을 섞는 문제가 많은 도움이 되는 것 같다.