[백준][위상 정렬][힙] 1766 - 문제집

위상 정렬이란?

순서가 정해져 있는 작업을 차례로 수행해야 할 때, 순서를 결정해주는 알고리즘

최소힙인 heapq를 통해 위상 정렬 알고리즘을 구현할 수 있다.

 

시간복잡도

O(V+E)

V: 노드(=Vertex)

E: 간선(=Edge)

 

문제

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

1766번: 문제집

 

코드

import heapq

N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]  # 인덱스(노드)에 연결된 노드들
indegree = [0] * (N+1)  # 인덱스(노드)에 연결된 간선의 개수

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

# heapq에 들어가는 조건 -> 연결된 간선의 개수가 0인 노드들
heap = []
for i in range(1, N+1):
  if indegree[i] == 0:
    heapq.heappush(heap, i)

while heap:
  target = heapq.heappop(heap)
  print(target, end=' ')
  for i in arr[target]:
    indegree[i] -= 1
    if indegree[i] == 0:
      heapq.heappush(heap, i)

• 항상 문제를 모두 풀 수 있는 경우만 입력으로 주어지기 때문에 사이클이 발생하여
  1번 조건을 만족할 수 없는 상황은 생각하지 않아도 된다.
• 연결된 간선의 개수가 0인. 즉, indegree(인덱스)가 0인 노드를 heapq에 넣음으로 2번 조건을 만족한다.
• 최소힙의 속성 때문에 꺼낼 때 3번의 가능하면 쉬운 문제부터 푸는 조건을 만족한다.