#104 백준 파이썬 [1766] 문제집 - 위상정렬 + 힙

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

 

#Solution

해당 문제는 '사이클'이 없고 '방향'만 존재하는 그래프(DAG: Directed Acyclic Graph)에서 정점(Vertex)을 나열하는 방법으로 풀 수 있다. 이를 위상정렬 (Topological Sort)이라고 한다.

또한 힙을 이용해 우선순위 큐를 구현해 시간을 최소화해야한다.

 

0) 정점과 연결된 다른 정점 리스트, 정점에 들어오는 그래프 개수 리스트 2개를 만들어준다.

1) 진입 루트(Indegree)가 없는 정점을 먼저 최소 힙에 넣어준다.

2) 해당 정점과 연결되어있는 노드에서 진입 루트 개수를 하나씩 빼준다.

3) 최소 힙을 출력(heappop)해주고 다시 1)로 돌아가고 힙이 빌 때까지 반복한다.

 

힙을 이용한 우선순위큐를 이용하지 않으면 너무 많은 시간이 걸린다. 또한 만들어준 힙에 데이터를 넣으면 리스트 내의 가장 작은 값을 가장 앞으로 옮겨준다. min(list) 함수가 O(n)이라면 최소 힙은 O(log(n))의 시간이 걸린다. min함수를 사용하면 O(n^2)이 되므로 무조건 힙을 이용해 시간을 줄여줘야한다.

import sys
import heapq

num_problem, num_compare = map(int, input().split())
problem_list = [[] for i in range(num_problem + 1)]
indegree = [0 for i in range(num_problem + 1)]
heap = []
result = []


#Graph Information
for i in range(num_compare):
    A, B = map(int, input().split())
    problem_list[A].append(B)
    indegree[B] += 1


#Make First heap
for i in range(1, num_problem + 1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)


#Make Topological Sort Loop
while heap:
    temp = heapq.heappop(heap)
    result.append(temp)
    for j in problem_list[temp]:
        indegree[j] -= 1
        if indegree[j] == 0:
            heapq.heappush(heap, j)

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