자바 코딩테스트 강좌, 벨만-포드

코딩 테스트에 자주 등장하는 알고리즘 중 하나가 바로 벨만-포드 알고리즘입니다. 이 글에서는 벨만-포드 알고리즘의 개념, 작동 방법, 그리고 실제 문제에 적용하는 방법을 단계별로 설명하겠습니다. 코딩 테스트와 취업 준비에 유용한 정보를 제공하기 위해 다양한 예제와 함께 상세한 풀이 과정을 포함시켰습니다.

벨만-포드 알고리즘 소개

벨만-포드 알고리즘은 가중치가 있는 그래프에서 단일 출발점(source)에서 다른 모든 정점까지의 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 음의 가중치가 있는 간선을 허용하지만, 음의 사이클이 포함된 경우에는 최단 경로를 제공할 수 없습니다. 따라서 알고리즘을 적용하기 전 그래프에 음의 사이클이 존재하는지 여부를 확인해야 합니다.

벨만-포드 알고리즘의 특징

정점 수가 V일 때, 시간 복잡도는 O(VE)입니다.
다리 데이터의 포맷이 다양할 수 있습니다.
최단 경로는 음의 가중치가 없는 그래프에서도 효과적으로 탐색이 가능합니다.
음의 사이클 검출 기능이 내장되어 있습니다.

문제: 최단 경로 찾기

다음은 벨만-포드 알고리즘을 이용하여 최단 경로를 찾는 문제입니다.

문제 설명

가중치가 있는 방향 그래프가 주어질 때, 특정 출발점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하세요. 그래프는 음의 가중치를 포함할 수 있습니다. 만약 음의 사이클이 존재하면, ‘Negative Cycle’이라는 메시지를 출력해야 합니다.

입력 형식

첫 번째 줄에는 정점의 수 V (1 ≤ V ≤ 1000)와 간선의 수 E (1 ≤ E ≤ 10,000)가 주어진다.
두 번째 줄에는 출발 정점 S (1 ≤ S ≤ V)가 주어진다.
이후 E줄에 걸쳐 각 간선에 대한 정보가 u, v, w (1 ≤ u, v ≤ V, -10^5 ≤ w ≤ 10^5)의 형태로 주어진다.

출력 형식

각 정점까지의 최단 경로 길이를, 공백으로 구분하여 출력한다.
음의 사이클이 존재하면 'Negative Cycle'를 출력한다.

문제 풀이

1. 문제 이해 및 분석

문제를 해결하기 위해 먼저 입력으로 주어지는 그래프 정보를 파악해야 합니다. 정점과 간선의 개수, 출발 정점을 이해해야 최단 경로를 구하는 과정으로 나아갈 수 있습니다. 이 문제는 벨만-포드 알고리즘의 기본적인 구조를 잘 활용해야 합니다.

2. 알고리즘 설계

벨만-포드 알고리즘은 다음의 단계로 진행됩니다:

모든 간선을 기반으로 최단 경로 값을 초기화합니다. 출발점은 0, 다른 모든 정점은 무한대(infinity)로 설정합니다.
정점의 수 – 1 만큼의 횟수 동안 모든 간선을 검사하고, 최단 경로를 갱신합니다.
모든 간선을 다시 검사하여, 최단 경로를 갱신할 수 있다면 음의 사이클이 존재하는 것으로 판단합니다.

3. 자바 코드 구현

이제 위에서 설명한 알고리즘을 바탕으로 자바 코드를 작성해 보겠습니다.

import java.util.*;

public class BellmanFord {
    static class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt(); // 정점의 수
        int E = sc.nextInt(); // 간선의 수
        int S = sc.nextInt(); // 출발 정점

        List edges = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int weight = sc.nextInt();
            edges.add(new Edge(u, v, weight));
        }

        int[] dist = new int[V + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        // 알고리즘 실행
        for (int i = 1; i <= V - 1; i++) {
            for (Edge edge : edges) {
                if (dist[edge.u] != Integer.MAX_VALUE && 
                    dist[edge.u] + edge.weight < dist[edge.v]) {
                    dist[edge.v] = dist[edge.u] + edge.weight;
                }
            }
        }

        // 음의 사이클 검출
        for (Edge edge : edges) {
            if (dist[edge.u] != Integer.MAX_VALUE && 
                dist[edge.u] + edge.weight < dist[edge.v]) {
                System.out.println("Negative Cycle");
                return;
            }
        }

        // 최단 경로 출력
        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("Infinity ");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }
}

4. 코드 설명

위 코드는 벨만-포드 알고리즘의 전체 흐름을 담고 있습니다:

우선 edge 리스트를 사용하여 모든 간선 데이터를 저장합니다.
거리 배열(dist)을 선언하고 출발점의 거리를 0으로 초기화합니다.
안쪽 loop에서 각 간선을 반복하며, 최단 거리를 갱신합니다.
모든 간선에 대해서 다시 검토한 후, 음의 사이클 여부를 확인합니다.

5. 테스트 및 검증

코드를 완성한 후, 다양한 테스트 케이스를 통해 알고리즘의 올바른 작동 여부를 확인해야 합니다. 예를 들어:

입력:
5 8
1
1 2 4
1 3 3
2 3 1
3 2 -1
2 4 2
3 4 5
4 5 -3
5 4 2

출력:
0 3 3 5 Infinity

6. 결론

벨만-포드 알고리즘은 최단 경로 문제를 해결하기 위해 매우 유용한 도구입니다. 음의 가중치를 허용하는 특성 덕분에 다양한 그래프 문제에 적용할 수 있습니다. 이 알고리즘의 이해와 구현은 코딩 인터뷰 및 알고리즘 시험에서 높은 점수를 얻기 위한 필수 능력 중 하나입니다.

마무리

벨만-포드 알고리즘에 대한 이번 강좌가 도움이 되셨다면 좋겠습니다. 코딩 테스트 준비에 실질적인 기여를 할 수 있기를 바랍니다. 알고리즘을 다양한 문제에 적용해 보며 심화 학습을 이어가세요!