파이썬 코딩테스트 강좌, 최단 경로 구하기

안녕하세요! 이번 글에서는 취업을 위한 알고리즘 시험 준비과정에 대해 이야기하고자 합니다. 특히, 최단 경로 구하기 알고리즘 문제에 대해 깊이 있게 다뤄보겠습니다. 이 문제는 다양한 상황에서 접할 수 있으며, 그래프 이론의 기본 개념인 최단 경로 알고리즘은 취업 인터뷰에서 자주 출제되는 문제입니다.

최단 경로 문제의 정의

최단 경로 문제는 주어진 그래프에서 두 노드 사이의 경로 중에서 가장 짧은 경로를 찾는 문제입니다. 여기서 그래프는 도로, 통신망 등의 네트워크를 수학적으로 표현한 것으로, 정점(vertex)과 간선(edge)으로 구성됩니다. 우리는 이 문제를 해결하기 위해 여러 가지 알고리즘을 사용할 수 있으며, 여기에서는 Dijkstra 알고리즘을 집중적으로 다룰 것입니다.

Dijkstra 알고리즘 이해하기

Dijkstra 알고리즘은 가중치가 있는 그래프에서 하나의 정점에서 다른 모든 정점까지의 최단 경로를 찾는 효율적인 알고리즘입니다. 이 알고리즘은 다음과 같은 방식으로 작동합니다:

1. 시작 정점을 선택하고, 해당 정점에 대한 거리를 0으로 설정합니다.
2. 시작 정점과 연결된 정점들의 거리를 갱신합니다.
3. 갱신된 거리 중 가장 짧은 정점을 선택하고, 그 정점을 ‘방문한 정점’으로 표시합니다.
4. 방문한 정점과 연결된 정점을 반복적으로 선택하여 거리를 갱신합니다.
5. 모든 정점이 방문될 때까지 이 과정을 반복합니다.

문제 제시

이번 강좌에서는 그래프가 주어졌을 때, 두 정점 간의 최단 경로를 구하는 문제를 다루겠습니다. 아래와 같은 형태로 문제를 정리할 수 있습니다:

5 7
0 1 2
0 2 3
1 2 1
1 3 5
2 4 2
3 4 1
4 3 3
0 4

문제 해결 과정

1. 그래프 구조 설정

우선, 위 문제를 해결하기 위해서는 그래프를 적절한 데이터 구조로 설정해야 합니다. 일반적으로 인접 리스트 형태를 사용하는 것이 메모리 및 처리 속면에서 효율적입니다. Python에서는 딕셔너리를 사용하여 구현할 수 있습니다.

2. Dijkstra 알고리즘 구현

다음으로 Dijkstra 알고리즘을 구현하기 위해 필요한 라이브러리는 다음과 같습니다:

import heapq
import sys
from collections import defaultdict

여기서 heapq는 우선순위 큐(priority queue)를 위해 사용하고, defaultdict는 인접 리스트를 쉽게 구현하기 위해 사용할 것입니다.

3. Python 코드 예제

이제 최단 경로를 구하는 전체 코드를 작성해보겠습니다:

def dijkstra(graph, start, end):
    # 거리 초기화
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    priority_queue = [(0, start)]  # (거리, 정점)

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

        # 현재 노드까지의 거리보다 큰 값이 들어온 경우 무시
        if current_distance > distance[current_node]:
            continue

        # 이웃 노드 방문
        for neighbor, weight in graph[current_node]:
            distance_via_neighbor = current_distance + weight
            if distance_via_neighbor < distance[neighbor]:
                distance[neighbor] = distance_via_neighbor
                heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))

    return distance[end]

# 그래프 정의
graph = defaultdict(list)
edges = [
    (0, 1, 2),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 5),
    (2, 4, 2),
    (3, 4, 1),
    (4, 3, 3)
]

for u, v, w in edges:
    graph[u].append((v, w))

# 최단 경로 계산
start, end = 0, 4
result = dijkstra(graph, start, end)
print(result)  # 출력 결과: 5

4. 코드 설명

위 코드는 Dijkstra 알고리즘을 사용하여 주어진 그래프에서 최단 경로를 구하는 과정입니다. 각 주석을 통해 코드를 단계별로 이해할 수 있지만, 여기서 간단히 요약하자면:

1. 그래프를 딕셔너리 형태로 설정합니다.
2. 시작 정점의 거리를 초기화하고, 우선순위 큐에 추가합니다.
3. 큐에서 정점을 꺼내 해당 정점의 이웃을 조사하여 거리 업데이트 및 큐에 추가합니다.
4. 모든 정점에 대한 거리를 계산한 후, 최종적으로 도착 정점의 거리를 반환합니다.

결론

최단 경로 구하기 알고리즘은 컴퓨터 과학의 중요한 주제 중 하나로, 간단하게 보일 수 있지만 실제로는 다양한 형태로 변형할 수 있습니다. Dijkstra 알고리즘 이외에도 Bellman-Ford, A* 알고리즘 등 여러 가지 방법이 존재합니다. 이번 글에서는 가장 기본적이고 널리 사용되는 Dijkstra 알고리즘에 대해 파헤쳐 보았습니다.

앞으로도 다양한 알고리즘 문제들을 함께 풀어나가며 더 심화된 내용도 다루어 보도록 하겠습니다. 감사합니다!