C# 코딩테스트 강좌, 벨만-포드

흔히 알고리즘 문제를 풀다 보면 다양한 최단 경로 문제를 마주하게 됩니다. 그 중에서도 “벨만-포드 알고리즘”은 음수 가중치 간선을 포함한 그래프에서 최단 경로를 찾는 데 유용한 알고리즘입니다. 이번 강좌에서는 벨만-포드 알고리즘에 대해 깊이 이해하고, 이를 활용한 문제를 하나 해결해 보도록 하겠습니다.

벨만-포드 알고리즘 소개

벨만-포드 알고리즘은 주어진 그래프에서 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다음과 같은 특징을 가지고 있습니다:

음수 가중치를 갖는 간선이 있는 그래프에서도 최단 경로를 찾을 수 있습니다.
음수 사이클이 존재하면, 최단 경로는 정의할 수 없습니다.
시간 복잡도는 O(VE)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다.

벨만-포드 알고리즘의 동작 원리

이 알고리즘은 다음과 같은 방법으로 동작합니다:

모든 정점의 거리 값을 무한대로 초기화합니다. 단, 시작 정점의 거리 값은 0으로 설정합니다.
모든 간선에 대해서, 해당 간선을 통해 이동할 수 있는 경우 거리 값을 업데이트합니다.
이 과정을 V – 1번 반복합니다. 왜냐하면 최장 경로는 V – 1개의 간선으로 이루어질 수 있기 때문입니다.
마지막으로, 음수 사이클이 존재하는지 확인하기 위해 한 번 더 모든 간선을 검사합니다.

문제 설명

문제: 최단 경로 찾기

주어진 그래프의 정점 N과 간선 M이 주어집니다. 시작 정점 S에서 다른 모든 정점까지의 최단 경로를 구하시오. 음수 가중치 간선이 있을 수 있으며, 음수 사이클이 존재할 경우 “Negative Cycle”를 출력합니다.

입력 예시 설명

위 입력 예시는 다음과 같은 그래프를 나타냅니다:

정점 수: 3

간선 수: 3

시작 정점: 1

1 ↔ 2 : 가중치 2
1 ↔ 3 : 가중치 3
2 ↔ 3 : 가중치 -5

코드 구현

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 입력 받기
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]); // 정점 수
        int M = int.Parse(input[1]); // 간선 수
        int S = int.Parse(input[2]); // 시작 정점

        // 그래프 초기화
        List> edges = new List>();
        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split();
            int u = int.Parse(input[0]); // 시작 정점
            int v = int.Parse(input[1]); // 도착 정점
            int w = int.Parse(input[2]); // 가중치
            edges.Add(Tuple.Create(u, v, w));
        }

        // 거리 배열 초기화
        int[] distance = new int[N + 1];
        Array.Fill(distance, int.MaxValue);
        distance[S] = 0;

        // 벨만-포드 알고리즘
        for (int i = 1; i <= N - 1; i++)
        {
            foreach (var edge in edges)
            {
                int u = edge.Item1;
                int v = edge.Item2;
                int w = edge.Item3;
                if (distance[u] != int.MaxValue && distance[u] + w < distance[v])
                {
                    distance[v] = distance[u] + w;
                }
            }
        }

        // 음수 사이클 체크
        bool hasNegativeCycle = false;
        foreach (var edge in edges)
        {
            int u = edge.Item1;
            int v = edge.Item2;
            int w = edge.Item3;
            if (distance[u] != int.MaxValue && distance[u] + w < distance[v])
            {
                hasNegativeCycle = true;
                break;
            }
        }

        // 결과 출력
        if (hasNegativeCycle)
        {
            Console.WriteLine("Negative Cycle");
        }
        else
        {
            for (int i = 1; i <= N; i++)
            {
                Console.WriteLine(distance[i] == int.MaxValue ? "INF" : distance[i].ToString());
            }
        }
    }
}

코드 설명

위 코드는 벨만-포드 알고리즘을 구현한 것입니다. 코드의 주요 부분을 설명하겠습니다.

List<Tuple<int, int, int>> edges: 간선 정보를 저장하기 위한 리스트입니다.
int[] distance: 각 정점까지의 최단 거리를 저장합니다. 초기값은 무한대로 설정하고, 시작 정점의 거리는 0으로 초기화합니다.
벨만-포드 알고리즘의 핵심인 반복문에서 각 간선을 검사하며 거리를 업데이트합니다.
마지막에는 음수 사이클이 존재하는지 확인하기 위해 한 번 더 간선을 검사합니다.

결론

이번 강좌를 통해 벨만-포드 알고리즘의 개념과 이를 활용한 문제를 해결하는 과정을 살펴보았습니다. 알고리즘의 원리를 깊이 이해하고 이를 코드로 구현하는 과정을 통해 코딩테스트에서의 응용 능력을 키울 수 있습니다.

벨만-포드 알고리즘은 실무에서도 여러 가지 최단 경로 문제를 해결하는 데 사용되므로, 이를 충분히 이해하고 연습하여 코딩테스트에 대비하시기 바랍니다.