[백준 1766 파이썬] 문제집 (골드 2, 위상 정렬)

알고리즘 유형 : 위상 정렬
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys, heapq
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
inDegree = [0]*(N+1)

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    inDegree[B] += 1

q = []

# 진입 차수가 0인 문제를 최소 힙에 넣어줌.
for idx in range(1, N+1):
    if inDegree[idx] == 0:
        heapq.heappush(q, idx)

res = []

while q:
    # 현재 최소 힙에 들어있는 진입 차수가 0인 문제들 중에서,
    # 문제 번호가 가장 작은(가장 쉬운) 문제를 뽑음
    quest = heapq.heappop(q)
    res.append(quest)
    
    for adj_quest in graph[quest]:
        inDegree[adj_quest] -= 1
        if inDegree[adj_quest] == 0:
            heapq.heappush(q, adj_quest)

print(*res)

풀이 요약

1. 위상 정렬 알고리즘에서, 진입 차수가 0인 노드를 일반적인 큐가 아닌 우선순위 큐(최소 힙)에 넣어주면 끝나는 문제이다.

2. b를 풀기 위해 a의 풀이가 선행되어야한다. 이 것은 a -> b의 단방향 간선을 의미하기도 한다.

   주어진 단방향 간선들을 모두 만족하도록 문제를 나열하면 되므로 위상 정렬을 적용하면 된다.

   다만 어떤 단계에서 선행 문제가 필요없이 바로 풀 수 있는 문제 중에서, 아무거나 뽑으면 안되고 그 중에서 문제 번호가 가장 작은, 즉 가장 쉬운 문제를 뽑아야한다. (조건 3)

   따라서 최소 힙을 사용해주면 됨

배운 점, 어려웠던 점

• 위상 정렬 알고리즘에서 최소 힙만 사용하면 되는 간단한 문제였다. 최소 힙을 사용하는 아이디어를 생각해내는 것도 그리 어렵지 않았다.