[BOJ, 백준] 1766 문제집 Python

 

 

 

 

도중까지 읽다가, 아 이거 위상정렬이군

 

하고 있었는데, 가능하면 쉬운 문제부터 풀어야한다는 점이 상당히 핵심적

그럼에도 불구하고 어렵지 않은 이유는, 

 

topological sorting에서 indegree가 0이 되는 것들을 우선적으로 넣고, 그 이후에 node를 방문하며 하나씩 간선을 제거해나가는 (indegree를 1씩 줄이는 방식)을 취하는 것인데 이 부분에서 Indegree가 0 이 되는 것을 heap에다가 넣어두면 되겠다.

 

Heap은 항상 최솟값을 뱉어내기 때문에, 3번 조건인 쉬운 문제부터 풀어야 한다를 풀기 최적화되어있는 알고리즘이겠다.

반대로, 어려운 문제부터 풀어야한다라면, 최대힙 (즉, 마이너스를 붙여서 저장하는 것)부터 활용하면 되겠다.

 

아래는 답안 코드

import sys
import heapq

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

for _ in range (M):
    a,b = map(int,input().split())
    indegree[b] += 1
    path[a].append(b)
    
prior_solving = []
for i in range (1, N+1):
    if indegree[i] == 0:
        heapq.heappush(prior_solving,i)

answer = []
while prior_solving:
    x = heapq.heappop(prior_solving)
    answer.append(x)
    
    for y in path[x]:
        indegree[y] -= 1
        if indegree[y] == 0:
            heapq.heappush(prior_solving,y)
            
print(*answer)