[백준 - Python] 1766 - 문제집

0.  문제 링크

 

 

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

1766번: 문제집

---

1.  풀이 방법

 

 

해당 문제는 위상 정렬 알고리즘을 사용해야 한다. 위상 정렬 알고리즘은 싸이클이 없는 그래프에서, 각 노드들이 순서를 지켜야 할 때 사용된다고 한다.

 

해당 문제의 풀이 방법은 다음과 같다.

1. 우선 나의 자식이 되는 문제들을 입력한다. -> 즉 인접한 노드를 입력한다.
2. 또한 자식 노드는 앞서서 몇 개의 문제를 풀어야 하는지 기록해 놓는다. -> degree
3. 이후 앞서 풀어야 되는 문제가 없는 문제들을 모두 출력한다.
4. 그와 동시에 나에게 자식 문제가 있다면, degree에서 -=1을 한다.
5. 만약 degree == 0이라면, 해당 문제도 이제 풀 수 있는 문제가 된다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline
import heapq


if __name__ == "__main__":
    n, m = map(int, input().split())
    subSequenceList = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)
    hp = []

    for _ in range(m):
        a, b = map(int, input().split())
        subSequenceList[a].append(b)        # 내 자식을 넣음
        degree[b] += 1      # 자식이 앞서서 몇 개의 문제를 풀어야 하는지

    for i in range(1, n + 1):
        if degree[i] == 0:      # 부모가 없는 문제
            heapq.heappush(hp, i)

    while hp:
        prior = heapq.heappop(hp)
        print(prior, end=' ')
        for sub in subSequenceList[prior]:      # 자식들의 단계를 한 단계 낮춤
            degree[sub] -= 1
            if degree[sub] == 0:
                heapq.heappush(hp, sub)     # 이제 부모가 없음 -> 출력해도 됨

---

3.  마무리

 

 

위상 정렬 문제 재밌는 것 같다.