[알고리즘] 백준 - 문제집

백준 - 문제집

내 풀이

'''
Problem Solving Baekjoon 1766
Author: Injun Son
Date: May 14, 2020
'''

from collections import deque
import heapq

N, M = list(map(int, input().split()))
problems = [0] * (N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = list(map(int, input().split()))
    graph[a].append(b)
    problems[b] += 1

for i in range(1, N+1):
    graph[i].sort()

heap = []
result = []

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

while heap:
    node = heapq.heappop(heap)
    result.append(node)
    for adj_node in graph[node]:
        problems[adj_node] -= 1
        if problems[adj_node] == 0:
            heapq.heappush(heap, adj_node)

print(' '.join(map(str, result)))

위상정렬에서는 큐를 사용했다. 따라서 여러개의 답이 나올 수 있었지만 이 문제에서는 여러 개의 답이 아닌, 낮은 숫자부터 나오게 했다. 따라서 힙을 사용했다.