99클럽 코테 스터디 4일차 TIL (벨만-포드)

벨만-포드 알고리즘

개념

최단 경로를 구하는 알고리즘으로 음의 가중치가 있는 경우에도 사용할 수 있는 알고리즘이다.

주로 음수 가중치가 있는 그래프에서 최단 경로를 찾거나, 사이클 유무를 판별하는 데 사용한다.

작동 원리

• 반복적인 최단 거리 갱신: 각 간선을 반복적으로 확인하고, 최단 경로가 발견될 때마다 경로를 갱신한다.
• 음수 사이클 탐지: N-1 번의 반복 후에도 경로가 더 줄어드는 경우, 음수 사이클이 존재한다고 판단한다.
• 시간 복잡도: O(V * E)로, 모든 간선을 반복 확인하기 때문에 크기가 큰 그래프에서는 효율성이 떨어진다.

구현 코드 - JAVA

for (int i = 0; i < V - 1; i++) { // V-1번(자신의 노드를 제외한 탐색) 반복
    for (Edge edge : edges) {
        int u = edge.start; // 시작점
        int v = edge.end; // 도착지
        int weight = edge.weight; // 가중치
        // 경유지 경로가 있고, 도착지로 바로 가는 것보다 경유지를 거쳐 가는 비용이 더 적을 경우
        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
            dist[v] = dist[u] + weight;
        }
    }
}

// 음수 사이클 체크
for (Edge edge : edges) {
    int u = edge.start;
    int v = edge.end;
    int weight = edge.weight;
    // 이미 최소거리를 구했는데 한 번 더 업데이트가 된다면 음수 사이클이 존재함.
    if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
        System.out.println("음수 사이클이 존재합니다.");
        break;
    }
}

문제

BOJ 1865 - 웜홀

해결 방법

1. 도로를 입력받으므로 무방향 그래프처럼 양쪽에 입력한다.
2. 웜홀의 경우 단방향 그래프로 한쪽에만 입력한다.
3. 벨만-포드 알고리즘을 사용하여 한 위치에서 시작하는 최단 거리를 구한다.
   • 하나의 노드에서만 탐색해도 음의 사이클이 존재하는지 확인할 수 있으므로 시간초과를 막기 위해 1번 노드에서 탐색하도록 구현한다.
4. 최단 거리로 업데이트된 내용에서 탐색을 한 번 더 진행하여 값이 변경된다면 음의 사이클을 가지고 있으므로 YES 를 출력하도록 한다.

정답 코드 - JAVA

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int W;
    static int[][] graph;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());
        while (TC > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            graph = new int[N + 1][N + 1];
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    graph[i][j] = (int)1e9;
                }
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());

                graph[a][b] = Math.min(graph[a][b], c);
                graph[b][a] = Math.min(graph[b][a], c);
            }

            for (int i = 0; i < W; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());

                graph[a][b] = Math.min(graph[a][b], -c);
            }

            if (bellmanFord()) {
                sb.append("YES").append("\n");
            } else {
                sb.append("NO").append("\n");
            }
            TC--;
        }

        bw.write(String.valueOf(sb));
        bw.newLine();
        bw.flush();
    }

    static boolean bellmanFord() {
        int[] dist = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[1] = 0;
        boolean isUpdated = false; // 경로 갱신 여부
        for (int i = 1; i < N; i++) { // 현재 노드를 제외한 나머지 노드만큼 반복
            isUpdated = false;
            for (int v = 1; v <= N; v++) { // 경유지
                for (int u = 1; u <= N; u++) { // 도착점
                    if (dist[u] > dist[v] + graph[v][u]) {
                        dist[u] = dist[v] + graph[v][u];
                        isUpdated = true; // 경로가 갱신됨
                    }
                }
            }
            // 경로가 갱신된적이 없다면 불가능하므로 탐색종료
            if (!isUpdated) {
                return false;
            }
        }
        if (isUpdated) { // 갱신되었다면 음의 사이클 확인
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dist[i] + graph[i][j] < dist[j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

오늘의 회고

벨만-포드 알고리즘에 대해 다시 공부하고 이를 문제에 적용했다. 처음에는 전체 노드에서 탐색을 시도하다 시간 초과가 발생하였고, 인터넷의 도움을 받아 하나의 노드에서만 검색해도 음의 사이클이 존재하는지 확인할 수 있다는 것을 알게 되었다.