백준 1766번 문제집

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

1766번: 문제집

백준 2252번 줄 세우기 문제와 같이 기본적인 위상정렬 알고리즘을 연습해볼 수 있는 문제다.

 

백준 2252번 문제와 다른점은 2252번 문제는 가능한 정답 중에 하나만 출력해도 정답으로 인정이 되었지만 1766번 문제는 출력의 순서에 신경을 써야 한다는 점이다.

 

문제의 조건이 '가능한 낮은 난이도의 문제를 먼저 푸는것'임으로 위상 정렬상으로는 같은 순서여도 문제의 번호가 작은 수라면 먼저 출력을 해야 한다.

 

기본적인 위상 정렬 코드에서 q 부분을 heapq로 바꿔주면 바로 해결되는 문제다

 

# 기본적인 위상정렬 코드는 나동빈님의 '이것이 취업을 위한 코딩테스트다'를 참조함
import heapq
import sys
input = sys.stdin.readline
v,e = map(int,input().split())

indegree = [0] * (v+1)

graph = [[] for i in range(v+1)]

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

    indegree[b] += 1

def topology_sort():
    result = []
    q = []

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

    while q:

        now = heapq.heappop(q)
        result.append(now)

        for i in graph[now]:
            indegree[i] -= 1

            if indegree[i] == 0:
                heapq.heappush(q,i)

    for i in result:
        print(i,end=' ')

topology_sort()