[Python] 문제집 - 백준 (위상정렬)

해당 글은 백준 1766번 '문제집' 문제를 다룬다.

문제

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

1766번: 문제집

 

설명

해당 문제는 위상 정렬 알고리즘으로 해결할 수 있다. 

위상 정렬은 순서가 정해져있는 작업을 차례로 수행할 때 사용한다.

 

위상정렬의 전체적인 과정은 아래와 같다.

0. 그래프와 진입차수 리스트를 생성한다.

1. 진입차수가 0인 정점을 큐에 삽입한다.

2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거한다.

3. 제거한 후에 진입차수가 0인 정점을 큐에 삽입한다.

4.이후 2~3의 과정을 반복한다.

 

코드

import heapq

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

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

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

result = []
while queue:
    now = heapq.heappop(queue)
    result.append(now)
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            heapq.heappush(queue, i)

print(*result)