[다익스트라] 백준 1753 최단경로

이번 포스팅에서는 백준 1753번 문제를 다익스트라 알고리즘을 활용하여 풀이하는 방법을 다뤄보겠습니다. 이 문제는 특정 시작점에서 다른 모든 정점으로 가는 최단 경로를 찾는 문제로, 그래프 이론에서 자주 등장하는 문제 유형입니다.

문제 설명

주어진 그래프에서 시작점으로부터 다른 모든 정점으로의 최단 경로를 구하는 문제입니다. 그래프는 방향성이 있으며, 간선마다 가중치가 부여되어 있습니다. 다익스트라 알고리즘은 이와 같은 가중 그래프에서의 최단 경로 문제를 효율적으로 해결할 수 있는 알고리즘입니다.

다익스트라 알고리즘 개요

다익스트라 알고리즘은 그래프 이론에서 가장 널리 사용되는 최단 경로 탐색 알고리즘 중 하나입니다. 이 알고리즘은 가중치가 있는 그래프에서, 하나의 시작 정점으로부터 다른 모든 정점으로 가는 최단 경로를 찾는 데 사용됩니다. 다익스트라 알고리즘은 다음과 같은 기본 개념에 기초합니다:

1. 우선순위 큐: 다익스트라 알고리즘은 우선순위 큐를 사용하여 가장 가까운 정점을 선택하고, 그 정점에서 다른 정점으로의 최단 경로를 갱신하는 방식으로 동작합니다.

2. 탐욕적 접근법: 다익스트라 알고리즘은 현재까지 계산된 최단 경로를 이용해 다음 경로를 선택하는 탐욕적 접근법을 사용합니다. 즉, 매 단계마다 최단 경로를 확정 짓고, 이를 바탕으로 다음 경로를 탐색합니다.

3. 동작 방식:

   • 시작 정점으로부터의 최단 경로를 저장할 테이블을 초기화하고, 시작 정점의 거리를 0으로 설정합니다.
   • 우선순위 큐를 사용해, 현재 정점에서 연결된 다른 정점으로의 경로를 계산하고, 더 짧은 경로를 발견하면 해당 경로로 업데이트합니다.
   • 이 과정을 모든 정점에 대해 반복하여 최단 경로를 찾습니다.

다익스트라 알고리즘의 시간 복잡도와 공간 복잡도

1. 시간 복잡도:
   다익스트라 알고리즘의 시간 복잡도는 그래프를 구현하는 방식과 사용된 데이터 구조에 따라 달라집니다.

   • 일반적으로, 우선순위 큐로 최소 힙(Heap)을 사용할 때의 시간 복잡도는 O((E + V) log V)입니다. 여기서 V는 노드의 수, E는 간선의 수입니다.
   • 노드를 힙에서 추출하고 인접한 노드를 탐색하는 비용이 O(log V)이고, 이 과정이 모든 간선에 대해 이루어지므로 전체 복잡도는 O((E + V) log V)가 됩니다.

2. 공간 복잡도:
   공간 복잡도는 주로 그래프를 저장하는 데 필요한 메모리와 거리 테이블 및 우선순위 큐에 의해 결정됩니다.

   • 그래프는 인접 리스트로 구현되므로, 그래프를 저장하는 데 (O(V + E))의 공간이 필요합니다.
   • 최단 거리 테이블은 모든 노드에 대해 거리 정보를 저장하므로 (O(V))의 공간이 필요합니다.
   • 우선순위 큐에는 최대 (V)개의 노드가 들어가므로 (O(V))의 공간이 필요합니다.
   • 따라서, 전체 공간 복잡도는 (O(V + E))가 됩니다.

다익스트라 알고리즘 동작 예제

예를 들어, 다음과 같은 가중 그래프가 있다고 가정해봅시다:

• A -> B: 1
• A -> C: 4
• B -> C: 2
• B -> D: 5
• C -> D: 1

이 경우, A에서 D까지의 최단 경로를 찾는다면, 다익스트라 알고리즘은 다음과 같은 순서로 동작합니다:

1. 시작점 A에서 출발하여 인접한 노드인 B와 C로의 거리를 계산합니다. B까지의 거리는 1, C까지의 거리는 4입니다.
2. B에서 C로 가는 경로(2)를 더해 C로 가는 거리(1 + 2 = 3)를 업데이트합니다.
3. C에서 D로 가는 경로(1)를 더해 D로 가는 거리(3 + 1 = 4)를 계산합니다.
4. B에서 D로 직접 가는 경로(5)를 확인하지만, 이는 이미 계산된 거리보다 길기 때문에 업데이트하지 않습니다.

결과적으로, A에서 D로 가는 최단 경로는 A -> B -> C -> D로, 거리는 4가 됩니다.

코드 설명

이제 이를 코드로 구현한 내용을 설명하겠습니다:

import heapq, sys

def dijkstra(num_nodes, edges, start_node):
    # 그래프 초기화
    graph = {i: [] for i in range(1, num_nodes + 1)}
    for u, v, w in edges:
        graph[u].append((v, w))

    # 최단 거리 테이블을 무한대로 초기화
    distances = {i: float('inf') for i in range(1, num_nodes + 1)}
    distances[start_node] = 0

    # 우선순위 큐 초기화
    priority_queue = [(0, start_node)]  # (거리, 노드)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

input = sys.stdin.readline
num_nodes, num_edges = map(int, input().split())
start_node = int(input())
edges = []

for _ in range(num_edges):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

shortest_distances = dijkstra(num_nodes, edges, start_node)

for node in range(1, num_nodes + 1):
    if shortest_distances[node] == float('inf'):
        print("INF")
    else:
        print(shortest_distances[node])

코드의 주요 동작 원리:

1. 그래프 초기화:

   • 주어진 노드와 간선 정보를 바탕으로 그래프를 인접 리스트 형태로 초기화합니다. 그래프는 딕셔너리로 구현되며, 각 노드는 연결된 노드와 간선의 가중치를 리스트 형태로 가지고 있습니다.

2. 최단 거리 테이블 초기화:

   • 모든 노드의 최단 거리를 무한대로 초기화하고, 시작 노드의 거리는 0으로 설정합니다. 이 테이블은 알고리즘이 진행됨에 따라 각 노드로의 최단 거리를 저장하는 데 사용됩니다.

3. 우선순위 큐를 이용한 최단 경로 탐색:

   • 우선순위 큐(최소 힙)를 사용하여 현재까지의 최단 거리를 기준으로 탐색할 노드를 선택합니다. 현재 노드에서 인접한 노드로의 거리를 계산하고, 이 거리가 기존에 알고 있던 거리보다 짧다면 갱신합니다.
   • 이 과정을 모든 노드를 방문할 때까지 반복합니다.

4. 결과 출력:

   • 최종적으로 각 노드로의 최단 거리를 출력합니다. 만약 특정 노드로의 거리가 갱신되지 않았다면, 해당 노드는 도달할 수 없는 노드로 간주하고 "INF"를 출력합니다.

결론

위 코드에서는 다익스트라 알고리즘을 이용하여 그래프에서의 최단 경로 문제를 해결했습니다. 다익스트라 알고리즘은 우선순위 큐를 사용하여 효율적으로 최단 경로를 찾는 알고리즘으로, 가중치가 있는 그래프에서의 경로 탐색에 매우 유용합니다. 이 문제를 통해 그래프 이론의 기본적인 개념과 다익스트라 알고리즘의 동작 원리를 이해할 수 있으며, 시간 복잡도와 공간 복잡도도 고려해야 하는 점을 유념해야 합니다.