악곱 == 악성곱슬

위상정렬, 우선순위 큐

---

이 문제는 대표적인 위상정렬 문제에 문제 난이도에 따른 우선순위를 부여한 문제이다.

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

문제의 조건중 다 풀어야 한다는 것을 제외하고 위 1번 조건을 통해 위상 정렬임을 알 수 있고, 2번을 통해 문제의 난이도를 key로 사용하는 min-heap을 통해 풀면 됨을 알 수 있다.

따라서 in_degree가 0이 된 노드를 queue가 아닌 min-heap에 차례대로 삽입하여 구현한다.

구현

---

import sys
import heapq

def solution(n):
    heap = []
    answer = ""
    for i in range(1, n+1):
        if not in_degree[i]:
            heapq.heappush(heap, i)
    while heap:
        cur_node = heapq.heappop(heap)
        answer += str(cur_node) + " "
        for to_node in connections[cur_node]:
            in_degree[to_node] -= 1
            if not in_degree[to_node]:
                heapq.heappush(heap, to_node)
    print(answer)

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    in_degree = [0] * (N + 1)
    connections = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, sys.stdin.readline().rstrip().split())
        in_degree[B] += 1
        connections[A].append(B)
    solution(N)