[BOJ/백준] 1766 문제집

import sys
import heapq

def input():
    return sys.stdin.readline().rstrip()

def solution():
    priority_que = []
    for num in range(1,N+1):
        if not indegree[num]:
            priority_que.append(num)
    heapq.heapify(priority_que)

    result = []
    while priority_que:
        num = heapq.heappop(priority_que)
        result.append(num)
        for next_num in graph[num]:
            indegree[next_num] -= 1
            if not indegree[next_num]:
                heapq.heappush(priority_que,next_num)
    return result

N,M = map(int,input().split())

graph = [ [] for _ in range(N+1)]
indegree = [0 for _ in range(N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    indegree[y] += 1

print(*solution())

문제를 읽어보면 순서가 정해져있고, 앞선 문제를 풀어야지 뒤의 문제를 풀 수 있다고 되어 있다.

 

이 문구를 보고 위상정렬임을 알 수 있고, 위상정렬 해주면 된다.

 

문제 난이도가 골드2 이지만, 골드2 수준은 아닌 듯한 문제였다. queue 대신 heapq를 쓰면 풀리는 문제라,

 

위상 정렬에 대해 알고 있으면 쉽게 풀릴 수 있는 문제라 생각한다.