[코딩테스트 cheatsheet] 다익스트라

개념

한 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘

현재 노드에서 가장 가까운 노드를 계속 탐색하며 최단거리를 그리디하게 업데이트해나감

힙을 사용하지 않으면 다음 노드를 선택하는 과정에서 연결된 노드를 모두 살펴야 함으로 비효율적

주의 : 가중치가 음일 경우 불가능함 => 벨만 포드 알고리즘을 사용해야함

 

시간복잡도 : O(ElogV) E : 간선의 개수, V : 노드의 개수 (힙 사용시)

 

코드

import heapq

# 입력값은 인접리스트 형식으로
graph = [[] for _ in range(n + 1)]

# 거리테이블을 무한으로 초기화
INF = int(1e9)
distance = [INF] * (n + 1)

# (거리, 노드)로 힙에 추가 -> 가장 가까운 거리를 바로 알 수 있음
start = 0
heap = []
heapq.heappush(heap, (0, start))

while heap:
    dist, now = heapq.heappop(heap)
    
    if distance[now] < dist:
    	continue
       
    for i in graph[now]:
        cost = dist + i[1]
        if distance[i[0]] > cost:
            distance[i[0]] = cost
            heapq.heappush(heap, (cost, i[0])
        
print(distance)

 

백준 티어별로 살펴보는 문제 유형

 

골드 5

5972 - 택배 배송 (https://www.acmicpc.net/problem/5972)

다익스트라를 알고 있다면 쉽게 풀리는 문제

 

골드 4

1504 - 특정한 최단 경로

 

골드 3

11779 - 최소비용 구하기 2 (https://www.acmicpc.net/problem/11779)

 

골드 2

2211 - 네트워크 복구 (https://www.acmicpc.net/problem/2211)

9370 - 미확인 도착지 (https://www.acmicpc.net/problem/9370)

 

골드 1 

1162 - 도로포장 (https://www.acmicpc.net/problem/1162)

1800 - 인터넷 설치 (https://www.acmicpc.net/problem/1800)

 

플래티넘 5

5719 - 거의 최단 경로 (https://www.acmicpc.net/problem/5719)

 

 

문제 접근법