[ 1766 ] [ 위상 정렬 ] 문제집

https://www.acmicpc.net/problem/1766

1766번: 문제집

---

풀이 과정

---

1. 문제를 푸는 순서가 있으므로 위상정렬 방식으로 풀이하는것이 좋음. 단, 문제 난이도가 낮은 것(번호가 작은 것)부터 풀어야 하므로 최소 히프를 사용하여서 구현함.
2. 문제들의 연결 정보와 각 문제의 진입 차수를 따로 저장한다.
3. 초기에 진입 차수가 0인 문제들을 히프에 넣는다.
4. 히프에서 문제 하나를 꺼내고, 문제에 연결된 다른 문제들(해당 문제를 푼 다음에 풀 문제들)의 진입차수를 하나 낮추어 준다.
   1. 이 때, 진입차수가 0이 된다면 해당 문제 번호를 히프에 넣어준다.
   2. 히프에서 문제를 꺼낼 때 따로 리스트에 문제 번호를 저장해주어야 함.(정답에서 출력)

---

소스 코드

---

import heapq
import sys

input = lambda: sys.stdin.readline().rstrip()
n, m = map(int, input().split())

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

solve = []
heap = []

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

while heap:
    problem_number = heapq.heappop(heap)
    solve.append(problem_number)
    for next_problem in graph[problem_number]:
        indegree[next_problem] -= 1
        if indegree[next_problem] == 0:
            heapq.heappush(heap, next_problem)

print(*solve)