파이썬 코딩테스트 강좌, 다익스트라

안녕하세요, 여러분! 오늘은 다익스트라 알고리즘에 대해 깊이 있게 알아보고, 실제 코딩 테스트에서 자주 출제되는 문제를 풀어보도록 하겠습니다. 다익스트라 알고리즘은 가중치가 있는 미그래프에서 최단 경로를 찾는 알고리즘으로, 주로 네트워크 최단 경로 문제를 해결하는 데 사용됩니다.

1. 다익스트라 알고리즘 개요

다익스트라 알고리즘은 1956년 에드가 다익스트라에 의해 개발된 최단 경로 알고리즘으로, 특정 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 음수 가중치를 허용하지 않으며, 그래프가 연결되어 있다고 가정합니다.

1.1 알고리즘 동작 원리

시작 정점을 선택하고, 그 정점의 거리를 0으로 설정합니다.
나머지 모든 정점의 거리를 무한대로 초기화합니다.
최소 거리가 결정되지 않은 정점 중에서 가장 거리가 짧은 정점을 선택합니다.
선택된 정점을 기준으로 인접 정점들의 거리를 업데이트합니다.
모든 정점의 거리가 결정될 때까지 반복합니다.

2. 문제 설명

이제 실제 문제를 통해 다익스트라 알고리즘을 적용해봅시다.

문제: 최단 경로 찾기

입력으로 주어진 그래프가 주어졌을 때, 특정 시작 정점에서 모든 다른 정점까지의 최단 경로를 구하는 프로그램을 작성하시오.

입력 조건

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20, 1 ≤ E ≤ 100)
둘째 줄부터 E개의 줄에 걸쳐 각각의 간선에 대한 정보가 주어진다. 간선의 정보는 시작 정점 A, 도착 정점 B, 가중치 C 형태로 주어진다.
마지막 줄에는 시작 정점 K가 주어진다.

출력 조건

시작 정점 K에서 다른 모든 정점까지의 최단 거리를 출력합니다. 만약 어떤 정점까지의 경로가 없다면 INF를 출력합니다.

3. 문제 풀이 과정

3.1 그래프 표현

우선 주어진 간선 정보를 바탕으로 그래프를 인접 리스트로 표현합니다. 파이썬에서는 딕셔너리(Dictionary)를 사용하여 각 정점과 그 정점과 연결된 다른 정점 및 가중치를 저장할 수 있습니다.

from collections import defaultdict
import heapq

def create_graph(edges):
    graph = defaultdict(list)
    for A, B, C in edges:
        graph[A].append((B, C))
    return graph

3.2 다익스트라 알고리즘 구현

이제 실제 다익스트라 알고리즘을 구현합니다. 이 알고리즘은 우선순위 큐를 활용하여 현재까지의 최단 경로를 효율적으로 업데이트합니다.

def dijkstra(graph, start, V):
    distances = {vertex: float('inf') for vertex in range(1, V + 1)}
    distances[start] = 0
    priority_queue = [(0, start)]

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

        if current_distance > distances[current_vertex]:
            continue

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

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

    return distances

3.3 최종 코드

모든 요소를 종합하여 최종적인 코드를 작성합니다. 입력을 받고 결과를 처리하는 부분도 포함되어 있습니다.

def main():
    V, E = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(E)]
    K = int(input())

    graph = create_graph(edges)
    distances = dijkstra(graph, K, V)

    for vertex in range(1, V + 1):
        if distances[vertex] == float('inf'):
            print("INF")
        else:
            print(distances[vertex])

if __name__ == "__main__":
    main()

4. 시간 복잡도

다익스트라 알고리즘의 시간 복잡도는 사용된 데이터 구조에 따라 달라집니다. 일반적으로 우선순위 큐를 사용할 경우 O((V + E) log V)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다.

5. 결론

이번 강좌에서 다익스트라 알고리즘을 통해 최단 경로 문제를 해결하는 방법을 배우고, 실제 입력을 다루어 보았습니다. 이 알고리즘은 네트워크, 게임 개발 등 다양한 분야에서 활용될 수 있으므로, 잘 숙지해두면 좋습니다.

추가 문제를 통해 더 다양한 상황을 연습해 보시기 바랍니다. 다음 강좌에서는 다른 알고리즘을 살펴보도록 하겠습니다. 감사합니다!