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

📌 최단경로 알고리즘

SWEA 의 1249. 보급로 라는 문제를 풀면서 가장 작은 비용으로 목표에 도달하는 최단경로 알고리즘을 찾아보았다. 그래서 정리하는 다익스트라 알고리즘으로 최단경로 구현하기.

일단 최단경로를 구하는 방법은 첫 정점을 기준으로 연결되어 있는 정점을 추가해가며, 최단거리를 갱신하는 것이 핵심이다.

1. 첫 정점부터 각 노드간의 거리를 저장하는 배열을 생성한다.
2. 첫 정점의 인접 노드간의 거리부터 계산하면서 가장 짧은 거리를 해당 배열에 업데이트 한다.

첫 정점부터 각 노드간의 거리를 저장하는 배열을 만들고, 각 노드까지 도달하는 최소 거리를 비교해가며 업데이트를 하면 되는데 이를 위해서 거리저장배열과 우선순위 큐가 필요하다.

📌 heapq 라이브러리 활용하기

heapq는 소트와 달리 전체를 정렬하는 것이 아니라, 가장 작은 값을 가지는 원소를 맨 앞에 정렬한다는 것이 주의!

import heapq

queue = []

heapq.heappush(queue, [2, 'A'])
heapq.heappush(queue, [5, 'B'])
heapq.heappush(queue, [1, 'C'])
heapq.heappush(queue, [7, 'D'])
print(queue)
for index in range(len(queue)):
    print(heapq.heappop(queue))
    
    
> [[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']]
  [1, 'C']
  [2, 'A']
  [5, 'B']
  [7, 'D']

📌 다익스트라 알고리즘

우선순위큐를 사용하기 때문에 지금까지 발견된 가장 짧은 거리의 노드에 대해 먼저 계산을 하고, 더 긴 거리로 계산된 루트에 대해서는 계산 스킵이 가능하다.

mygraph = {
    'A': {'B':8, 'C':1, 'D':2},
    'B' : {},
    'C': {'B':5, 'D':2},
    'D': {'E':3, 'F':5},
    'E': {'F':1},
    'F': {'A':5}
}

import heapq

def dijkstra(graph, start):
    
    # 초기화
    
    # 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장. 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [] # 우선순위 큐
    heapq.heappush(queue, [distances[start], start]) # 우선순위 큐에 첫 정점 저장
    
    # 우선순위 큐가 빌 때까지 노드를 꺼낸다.
    while queue:
        current_distance, current_node = heapq.heappop(queue) # 우선순위 큐에서 꺼낸 첫 정점의 거리와 번호
        
        if distances[current_node] < current_distance:
            continue
        
        # 배열에서 꺼낸 첫 정점거리 + 배열에서 꺼낸 첫 정접부터 연결된 노드까지 거리를 더해서 distance 라는 변수에 저장
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            # 첫 정점에서 인접한 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지 거리를 비교
            if distance < distances[adjacent]:
                # 현재 배열에 저장되어 있는 첫 정점에서 인접한 노드로 가는 거리가 더 짧으면 배열을 업데이트
                distances[adjacent] = distance
                # 우선순위 큐에도 추가한다.
                heapq.heappush(queue, [distance, adjacent])
                
    return distances
    
dijkstra(mygraph, 'A')


> {'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

📌 다익스트라로 풀어본 <1249. 보급로>

import heapq
T = int(input())
for tc in range(1, T+1):
    N = int(input())
    roads = [list(map(int, input())) for _ in range(N)]
    times = [[float('inf')]*N for _ in range(N)]
    times[0][0] = 0
    dir = [(-1,0), (1,0), (0,-1), (0,1)] # 상하좌우
    queue = []
    heapq.heappush(queue, (0, 0, times[0][0])) # x좌표, y좌표, 복구에 걸리는 시간

    while queue:
        x, y, time = heapq.heappop(queue)
        if times[x][y] < time:
            continue

        for d in dir:
            nx, ny = x + d[0], y + d[1]
            setting = time
            if 0 <= nx < N and 0 <= ny < N:
                setting += roads[nx][ny]

                if setting < times[nx][ny]:
                    times[nx][ny] = setting
                    heapq.heappush(queue, (nx, ny, setting))

    print(f'#{tc} {times[N-1][N-1]}')