20250121 이것이 코딩 테스트다 챕터9(최단 경로), 파이썬 heapq 모듈

January 21, 2025

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘.
길 찾기 문제라고도 불림.
실제 코딩테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제됨.

다익스트라 최단 경로 알고리즘

Dijkstra(데이크스트라) 최단 경로 알고리즘.
그래프에서 여러 개의 노드(각 지점 cf. 지점간 연결된 도로 : 간선)가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 거리를 구해주는 알고리즘.

음의 간선 : 0보다 작은 값을 가지는 간선을 의미함.

‘음의 간선’이 없을 때 정상적으로 동작.
매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 ‘그리디 알고리즘’으로 분류됨.

원리

출발 노드 설정
최단 거리 테이블 초기화
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
해당 노드 거쳐 다른 노드로 가는 비용 계산해 최단 거리 테이블 갱신
3 ~ 4 반복

최단 경로를 구하는 과정에서 ‘각 노드(지점)에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있음.
매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인함.
나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 ‘더 짧은 경로도 있었네? 이제부터는 이 경로가 제일 짧은 경로야’라고 판단하는 것. 따라서 ‘방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인’해 그 노드에 대하여 4번 과정을 수행한다는 점에서 그리디 알고리즘으로 볼 수 있음.
직접 해보면 한번 방문한 노드의 ‘최단 거리가’는 감소하지 않는 것을 볼 수 있음.
따라서 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해해도 됨.

구현방법

다익스트라 알고리즘을 구현하는 방법은 2가지.

구현하기 쉽지만 느리게 동작하는 코드 (간단한 다익스트라 알고리즘)
구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드 ⭐

방법2를 정확히 이해하고 구현할 수 있을 때까지 연습해야 됨.
최단 경로 알고리즘을 응용해서 풀 수 있는 고난이도 문제들이 많으므로 방법2를 이해하고 정확히 구현할 수 있으면 다양한 고난이도 문제를 만났을 때 도움을 얻을 수 있음.

int(1e9) : 초기화 값 무한. (1,000,000,000 = 10억)

간단한 다익스트라 알고리즘

시간복잡도 O(V^2), V는 노드의 개수
=> 노드 개수 5,000개 이하면 이 방법 가능. 10,000개 넘어가면 이 코드 불가능.
각 노드에 대한 최단 거리를 담는 1차원 리스트 선언, 단계마다 ‘방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택’하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)

소스코드

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드 개수, 간선 개수 입력받기
n, m = map(int, input().split())
# 시작 노드 번호 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보 담는 리스트 만들기
graph = [[] for i in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
  a, b, c = map(int, input().split())
  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
  graph[a].append((b, c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
  min_value = INF
  index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
  for i in range(1, n + 1):
    if distance[i] < min_value and not visited[i]:
      min_value = distance[i]
      index = i
  return index

def dijkstra(start):
  # 시작 노드에 대해서 초기화
  distance[start] = 0
  visited[start] = True
  for j in graph[start]:
    distance[j[0]] = j[1]
  # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
  for i in range(n - 1):
    # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
    now = get_smallest_node()
    visited[now] = True
    # 현재 노드와 연결된 다른 노드를 확인
    for j in graph[now]:
      cost = distance[now] + j[1]
      # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
      if cost < distance[j[0]]:
        distance[j[0]] = cost

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
  # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
  if distance[i] == INF:
    print("INFINITY")
  # 도달할 수 있는 경우 거리를 출력
  else:
    print(distance[i])

개선된 다익스트라 알고리즘

O(ElogV), V는 노드의 개수, E는 간선의 개수.
힙(heap) 자료구조 사용.
-> 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있음.

힙(우선순위 큐)

우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나.

스택 : 가장 ‘나중에 삽입된’ 데이터 가장 먼저 삭제
큐 : 가장 ‘먼저 삽입된’ 데이터 가장 먼저 삭제
우선순위 큐 : ‘우선순위가 가장 높은’ 데이터 가장 먼저 삭제

PriorityQueue 혹은 heapq 라이브러리를 사용해서 구현.
heqpq가 더 빠르게 동작하기 때문에 수행 시간이 제한된 상황에서는 heapq 사용 권장.
우선순위 큐 라이브러리에 데이터를 묶음으로 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정함. (ie. 튜플 데이터(거리, 노드번호)를 넣으면 거리순으로 정렬함)
시간 복잡도 삽입 O(logN), 삭제 O(logN), 총 O(NlogN)

최소 힙 : 우선순위 값이 낮은 데이터가 먼저 삭제. 디폴트
최대 힙 : 우선순위 값이 큰 데이터가 먼저 삭제.
파이썬 라이브러리에서는 최소 힙 구조가 디폴트. 다익스트라 최단 경로 알고리즘에서도 비용이 적은 노드를 우선하여 방문(최소 힙)하므로 파이썬 우선순위 큐 라이브러리 그대로 사용하면 적합.

cf. 최소 힙을 최대 힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용할 수 있음. 이런 테크닉도 실제 코테에서 자주 사용하기 때문에 기억해 둘것.

cf. 우선순위 큐를 구현할 때 힙 자료구조를 사용한다 했지만, 사실 구현 방법은 다양함.
단순히 리스트를 이용해서 구현할 수도 있음. 하지만 리스트는 원소를 삭제하려고 할 때마다 모든 원소를 확인해서 우선순위가 가장 높은 것을 찾아야 하므로 최악의 경우 O(N)의 시간이 소요됨. 전체는 O(N^2)

구현 방법

최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블) 아까와 같이 그대로 이용.
현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐 추가로 이용.

소스코드

앞선 코드와 비교했을 때 get_smallest_node() 함수를 작성할 필요 없음.
‘최단 거리가 가장 짧은 노드를 선택’하는 과정을 dijkstra() 함수 안에서 우선순위 큐를 이용하는 방식으로 대체할 수 있기 때문.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
  a, b, c = map(int, input().split())
  # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
  graph[a].append((b, c))

def dijkstra(start):
  q = []
  # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q: # 큐가 비어있지 않다면
    # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heappop(q)
    # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
    if distance[now] < dist:
      continue
    # 현재 노드와 연결된 다른 인접한 노드들을 확인
    for i in graph[now]:
      cost = dist + i[1]
      # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
  # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
  if distance[i] == INF:
    print("INFINITY")
  # 도달할 수 있는 경우 거리를 출력
  else:
    print(distance[i])

파이썬 heapq 모듈

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.
아래에서는 heap이 빈 리스트이다.

heapq.heappush(heap, item) : item을 heap에 추가
heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N))

ex. heappush 예시

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

#### 출력
## [10, 50, 20]

ex. heappop 예시

result = heapq.heappop(heap)

print(result)
print(heap)

#### 출력
## 10
## [20, 50]

만약 원소를 삭제하지 않고 가져오고 싶으면 [0] 인덱싱을 통해 접근하면 된다.

result2 = heap[0]

print(result2)
print(heap)

#### 출력
## 20
## [20, 50]

ex. heapify 예시 : 이미 생성해둔 리스트가 있다면 heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.

heap2 = [50 ,10, 20]
heapq.heapify(heap2)

print(heap2)

최대 힙 만들기 : 힙에 원소를 추가할 때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다. 이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 되는 것이다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

#### 출력
## [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]

실제 원소 값은 튜플의 두 번째 자리에 저장되어 있으므로 [1] 인덱싱을 통해 접근하면 된다.

max_item = heapq.heappop(max_heap)
real_item = max_item[1]

print(max_item)
print(real_item)

#### 출력
## (-9, 9)
## 9

20250121 이것이 코딩 테스트다 챕터9(최단 경로), 파이썬 heapq 모듈

최단 경로 알고리즘

다익스트라 최단 경로 알고리즘

원리

구현방법

간단한 다익스트라 알고리즘

소스코드

개선된 다익스트라 알고리즘

힙(우선순위 큐)

구현 방법

소스코드

파이썬 heapq 모듈

Leave a comment

You may also enjoy

상태관리 라이브러리

IntersectionObserver와 debounce 방식

useOptimistic 훅

한글 두번 입력되는 오류 해결