파이썬 코딩테스트 강좌, 벨만-포드

코딩테스트 준비 과정에서 알고리즘은 매우 중요한 역할을 합니다. 특히, 그래프 관련 알고리즘은 많은 문제에서 자주 사용되며, 그중 벨만-포드 알고리즘은 최단 경로 문제를 해결하는 데 있어 매우 효율적입니다. 이번 강좌에서는 벨만-포드 알고리즘에 대해 상세히 알아보고, 이를 활용한 문제를 함께 풀어보겠습니다.

벨만-포드 알고리즘 이해하기

벨만-포드 알고리즘은 방향 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다음과 같은 특징이 있습니다:

간선의 가중치가 음수일 수 있지만, 음수 사이클이 존재하지 않아야 합니다.
시간 복잡도는 O(VE)입니다. 여기서 V는 정점의 수, E는 간선의 수를 의미합니다.
다익스트라 알고리즘과 달리, 다수의 출발 정점에서 최단 경로를 계산할 수 있습니다.

벨만-포드 알고리즘의 기본 아이디어는 다음과 같습니다. 각각의 정점에 대해 최단 경로를 업데이트하는 과정을 반복합니다. 이 과정을 V-1번 반복하여 최단 경로를 찾습니다. 만약 V-1번의 반복 후에도 경로가 업데이트된다면 음수 사이클이 존재한다는 의미입니다.

알고리즘 단계

벨만-포드 알고리즘의 기본적인 단계는 다음과 같습니다:

출발 정점에서의 거리를 0으로 초기화하고, 다른 모든 정점까지의 거리는 무한대로 설정합니다.
모든 간선에 대해 최단 경로를 반복적으로 업데이트합니다. V-1번 반복합니다.
마지막으로, 여전히 최단 경로가 업데이트된다면 음수 사이클이 존재하는 것입니다.

알고리즘 구현하기

이제 벨만-포드 알고리즘을 파이썬으로 구현해 보겠습니다. 아래는 벨만-포드 알고리즘의 간단한 구현 코드입니다.


def bellman_ford(graph, start):
    # Step 1: 초기화
    distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0

    # Step 2: 반복
    for _ in range(len(graph) - 1):
        for u, edges in graph.items():
            for v, weight in edges.items():
                if distance[u] != float('infinity') and distance[u] + weight < distance[v]:
                    distance[v] = distance[u] + weight

    # Step 3: 음수 사이클 검사
    for u, edges in graph.items():
        for v, weight in edges.items():
            if distance[u] != float('infinity') and distance[u] + weight < distance[v]:
                print("그래프에 음수 사이클이 있습니다.")
                return None

    return distance

실제 문제 해결하기

벨만-포드 알고리즘을 이해했으니, 이를 바탕으로 다음과 같은 문제를 해결해 보겠습니다.

문제: 최단 경로 찾기

다음과 같은 그래프가 주어졌을 때, A에서 다른 모든 정점까지의 최단 경로를 구하세요.


A --(1)--> B
A --(4)--> C
B --(2)--> C
C --(-5)--> D

여기서 각 간선은 (출발정점) –(가중치)–> (도착정점)의 형식으로 표시됩니다. 이 그래프는 A에서 출발하여 C와 D에 도달할 수 있는 모든 경로를 탐색해야 합니다. 특히 C에서 D로 가는 간선의 가중치가 음수입니다. 이 문제를 벨만-포드 알고리즘을 통해 해결해 봅시다.

문제 해결 과정

그래프를 정의합니다.
벨만-포드 알고리즘을 적용하여 최단 경로를 찾습니다.
결과를 출력합니다.

먼저, 그래프를 딕셔너리 형태로 정의합니다:


graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': 2},
    'C': {'D': -5},
    'D': {}
}

이제 베르만-포드 알고리즘을 사용하여 최단 경로를 구하는 코드를 작성합니다:


start_vertex = 'A'
shortest_paths = bellman_ford(graph, start_vertex)

if shortest_paths is not None:
    print("최단 경로:", shortest_paths)

결과 분석

위 코드를 실행하면 다음과 같은 최단 경로 결과를 얻을 수 있습니다:


최단 경로: {'A': 0, 'B': 1, 'C': 3, 'D': -2}

결과적으로, A에서 B로 가는 최단 경로는 1, B에서 C로 가는 최단 경로는 3, C에서 D로 가는 경로는 -2임을 확인할 수 있습니다.

결론

벨만-포드 알고리즘은 매우 유용하며 다양한 문제에 적용될 수 있는 알고리즘입니다. 이번 강좌를 통해 벨만-포드 알고리즘의 이해도를 높이고, 코딩테스트를 준비하는 데 큰 도움이 되었길 바랍니다. 이러한 알고리즘들을 충분히 연습하고 활용하는 것이 중요합니다.

더 많은 알고리즘 문제를 풀어보며 연습하고, 각 알고리즘의 특징과 동작 원리를 잘 이해하고 숙지하는 것이 코딩테스트 준비의 핵심입니다.