[백준] 1766번 문제집 - 파이썬(Python)

문제 (링크)

 

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

 

1766번: 문제집

 

나의 풀이

import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
in_degree = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())

    in_degree[b] += 1
    graph[a].append(b)

queue = []

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

while queue:
    current = heapq.heappop(queue)
    print(current, end=" ")

    for g in graph[current]:
        in_degree[g] -= 1

        if in_degree[g] == 0:
            heapq.heappush(queue, g)

코드 설명 및 풀이법

위상정렬 알고리즘의 아름다움에 빠져서 풀어본 문제이다.

 

일반적인 위상정렬과는 다르게, 2번 조건 때문에 매번 pop될 큐의 원소값은 최소값으로 갱신되어야한다.

 

약간 DFS와도 느낌이 비슷한데, 파이썬의 heapq 라이브러리를 사용해서 구현하였다. 

 

그 외에는 일반적인 위상정렬 알고리즘과 다르지 않다.