백준 1766 문제집

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1766

이 문제는 주어진 n개의 문제 중 순서에 맞게 먼저 풀어야 할 문제를 먼저 풀면서, 순서에 상관 없는 문제들은 숫자가 낮은 문제부터 풀어가는 내용이다.

풀이

난이도 : GOLD II

이 문제는 처음 보자마자 위상정렬을 떠올렸다.
그리고 남은 문제들을 우선순위가 높은 순서대로 뽑아내는 방법을 생각하다가 우선순위 큐를 사용하기로 하였다.

처음에는 우선순위 큐 안에 앞으로 풀어야 할 모든 문제들을 넣어두고, 우선순위에서 값을 꺼내면서 차수(indegree)를 확인하는 과정으로 풀이하였다.
하지만, 이 방법으로 풀이한 첫 풀이는 시간초과가 발생하였고, 시간초과를 개선하여 제출하여도 틀린 결과가 나와 다른 방법을 찾게 되었다.

그래서 사용한 방법이 우선순위 큐 안에 당장 풀 수 있는 문제들을 넣어두는 방법이다.

1) 위상정렬을 사용하기 위한 셋팅 (graph 입력, indegree)
2) 우선순위 큐 사용 (heapq로 우선순위 큐 구현)
3) 입력을 받은 후에 처음부터 차수가 0인 데이터를 우선순위 큐에 넣어준다.
4) 우선순위 큐에 값이 없어질 때까지 우선순위 큐에서 값을 하나씩 꺼내며 정답에 반영한다.
5) 또한 우선순위 큐에서 값을 빼내면 해당 문제를 풀었을 때의 차수를 감소시켜주었고, 차수가 0이 되는 경우라면 우선순위 큐에 그 문제를 추가해주었다.

✔ 주의할 점

• 이 문제는 input 양이 많으므로 sys.stdin.readline으로 입력받아야 한다.

코드

import heapq
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
q = []

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

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

results = []
while q:
    x = heapq.heappop(q)
    results.append(x)

    for g in graph[x]:
        indegree[g] -= 1
        if indegree[g] == 0:
            heapq.heappush(q, g)

print(" ".join(map(str, results)))