[백준 11779번 알고리즘 파이썬] 다익스트라 개념 설명 및 풀이

최단 경로 문제 해결하기: 다익스트라 알고리즘을 이용해 최소비용 구하기

이번 포스팅에서는 다익스트라 알고리즘을 이용해 특정 도시에서 다른 도시에 도달하는 데 필요한 최소 비용을 구하는 방법을 다루겠습니다. 이 문제는 특정 출발지에서 목적지까지의 최단 경로와 그 경로를 따르는 데 필요한 최소 비용을 계산하는 문제입니다. 주어진 코드는 이러한 문제를 해결하기 위한 일반적인 방법을 구현하고 있습니다.

 

문제 개요

이 문제에서는 n개의 도시와 m개의 버스가 주어지며, 각 버스는 특정 도시에서 다른 도시로 이동해 일정한 비용이 소요됩니다. 우리의 목표는 출발지에서 목적지까지의 최단 경로를 찾으면서, 그 경로를 통해 최소한의 비용으로 목적지에 도달하는 방법을 계산하는 것입니다.

 

코드 설명

주요 변수 설명

link: 각 도시에 연결된 다른 도시와 그 비용을 저장

dist: 특정 도시까지의 최소 비용을 저장하며 초기값은 비교를 위해 무한대(float('inf'))로 설정됨

parent: 최단 경로를 추적하기 위해 각 도시로 오기 직전의 도시를 저장함

q: 우선순위 큐로, 현재 방문할 도시와 그 도시까지의 누적 비용을 저장함

 

 

다익스트라 알고리즘의 기본 개념

다익스트라 알고리즘은 그래프 이론에서 최단 경로를 찾는 알고리즘 중 하나입니다. 이 알고리즘은 가중치가 있는 그래프에서, 출발 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 데 사용됩니다. 특히, 간선의 가중치가 모두 양수일 때 가장 효율적으로 작동합니다.

알고리즘의 동작 원리

다익스트라 알고리즘은 다음과 같은 단계로 작동합니다:

1. 초기화: 시작 노드에서 다른 모든 노드까지의 거리를 무한대로 설정하고, 시작 노드의 거리는 0으로 설정합니다. 시작 노드를 기준으로 최소 거리를 탐색하기 시작합니다.
2. 우선순위 큐 활용: 가장 거리가 짧은 노드를 우선적으로 처리하기 위해 우선순위 큐(보통 힙 자료구조)를 사용합니다. 큐에서 가장 작은 거리를 가진 노드를 꺼내어 그 노드와 연결된 인접 노드의 거리를 업데이트합니다. 완전 탐색을 사용하는 경우도 있을텐데 이 경우에는 시간복잡도가 커져 좋지 않습니다.
3. 거리 업데이트: 인접 노드까지의 거리가 기존에 저장된 거리보다 더 짧은 경우, 그 노드까지의 거리를 갱신하고, 해당 노드를 다시 큐에 추가합니다.
4. 반복: 모든 노드를 처리할 때까지 위 과정을 반복합니다. 큐가 비게 되면, 시작 노드에서 모든 노드까지의 최단 경로가 계산됩니다.

이 알고리즘은 시간 복잡도가 O((V + E) log V)로, 매우 효율적이며, 특히 노드가 많고 간선의 가중치가 양수인 그래프에서 널리 사용됩니다.

다익스트라 알고리즘은 보기보다 코드가 간단해서 금방 외우실 수 있습니다.

import sys
import heapq
input = sys.stdin.readline

def get_path(p, en):
    path = []
    while en != -1:
        path.append(en)
        en = p[en]
    path.reverse()
    return path

n = int(input().strip())
m = int(input().strip())

link = [[] for _ in range(n+1)]
dist = [float('inf')] * (n+1)
parent = [-1] * (n+1)
    
for _ in range(m):
    a, b, c = map(int, input().strip().split())
    link[a].append((b, c))

s, e = map(int, input().strip().split())
q = []
heapq.heappush(q, (0, s))
dist[s] = 0

while q:
    weight, node = heapq.heappop(q)
    
    if dist[node] < weight:
        continue
    
    for nxt, w in link[node]:
        if dist[node] + w < dist[nxt]:
            dist[nxt] = dist[node] + w
            heapq.heappush(q, (dist[nxt], nxt))
            parent[nxt] = node
            
path = get_path(parent, e)
print(dist[e])
print(len(path))
print(' '.join(map(str, path)))

 

get_path 함수 설명

get_path 함수는 최단 경로를 역추적하는 역할을 합니다. 다익스트라 알고리즘을 통해 각 노드까지의 최단 경로를 계산한 후, parent 리스트에 저장된 정보를 바탕으로 경로를 구성합니다.

• 파라미터: get_path(p, en) 함수는 parent 리스트 p와 목적지 노드 en을 입력받습니다.
• 경로 추적: 목적지 노드 en부터 시작하여 parent 리스트를 역추적하면서 경로를 구성합니다. parent[en]에는 en 노드로 오기 직전의 노드가 저장되어 있으므로, 이를 반복적으로 따라가면서 전체 경로를 추적합니다.
• 경로 생성: 추적된 경로는 역순으로 저장되므로, 마지막에 path.reverse()를 통해 올바른 순서로 변경합니다.

이 함수는 경로를 계산하는 데 필수적이며, 다익스트라 알고리즘의 결과로 최종 경로를 출력할 때 사용됩니다.

결론

이 포스팅에서는 다익스트라 알고리즘을 활용하여 도시 간의 최단 경로를 계산하고 그 경로의 최소 비용을 찾는 방법을 설명했습니다. 특히, get_path 함수를 통해 계산된 경로를 역추적하는 과정에서 최단 경로를 추출할 수 있음을 배웠습니다. 다익스트라 알고리즘은 다양한 그래프 기반 문제에서 최단 경로를 찾는 데 매우 유용한 도구입니다.