[백준 1865번 Java] 웜홀 - 벨만 포드(Bellman Ford)

문제 난이도

GOLD III (문제 링크)

 

 

풀이

[알고리즘] 벨만-포드(Bellman-Ford) 알고리즘

 

포스팅에서 학습했기 때문에 자세한 설명은 생략하고, 풀었던 방법만 나열해보고자 한다.

 

벨만-포드 알고리즘은 특정 출발점에서 모든 노드로의 최단 경로를 탐색하는 알고리즘이다. 또한 음수 사이클을 검출할 수 있다. 도달할 수 없는 노드를 표시하기 위해 INF에 가까운 값들로 초기화해서 사용할 수 있다.

 

 

첫번째 방법

문제에서, 특정 노드를 언급하지 않았다. 한 노드에서 출발하여~~~이기 때문에, 모든 노드를 출발지점으로 삼고 릴렉세이션을 한다면 쉽게 문제 해결을 할 수 있다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static class Edge {
        int from, to, cost;

        private Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }

    private static ArrayList<Edge> edgeList = new ArrayList<>();
    private static int[] dist;
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int TC = Integer.parseInt(br.readLine());

        StringTokenizer st;
        for (int i = 0; i < TC; i++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            dist = new int[N + 1];
            edgeList.clear();

            for (int j = 0; j < M; j++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());
                edgeList.add(new Edge(S, E, T));
                edgeList.add(new Edge(E, S, T));
            }
            for (int j = 0; j < W; j++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());
                edgeList.add(new Edge(S, E, -T));
            }

            boolean isYes = false;
            for (int j = 1; j <= N; j++) {
                if (bellmanFord(j, N)) {
                    bw.write("YES\n");
                    isYes = true;
                    break;
                }
            }

            if (!isYes) {
                bw.write("NO\n");
            }
        }

        bw.flush();
        bw.close();
    }

    private static boolean bellmanFord(int start, int N) {
        Arrays.fill(dist, INF);
        dist[start] = 0;

        // N-1번의 릴렉세이션(relaxation) 수행
        for (int i = 1; i < N; i++) {
            boolean updated = false;
            for (Edge edge : edgeList) {
                if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.cost) {
                    dist[edge.to] = dist[edge.from] + edge.cost;
                    updated = true;
                }
            }
            // 만약 이번 반복에서 업데이트가 없으면 종료
            if (!updated) break;
        }

        // 추가 릴렉세이션으로 음수 사이클 검증
        for (Edge edge : edgeList) {
            if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.cost) {
                return true; // 음수 사이클 존재
            }
        }

        return false;
    }
}

 

 

 

두번째 방법

첫 번째 방법처럼 모든 노드를 출발점으로 탐색하지 않아도, 음수 사이클 존재여부를 검출할 수 있는데, 음수 사이클이 존재하면 계속해서 전파된다는 특성을 이용해 접근이 가능하다. 우리는 음수 사이클 존재여부만 알면 된다.

 

이 때, 음수 사이클 존재 여부를 파악하기 위해 모든 간선을 검사해야 한다. 그러므로 기존 릴렉세이션을 사용하면 탐색되지 않은 경로에 음수 사이클이 있을 경우 놓칠 수 있다.

for (Edge edge : edgeList) {
    if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.cost) {
        dist[edge.to] = dist[edge.from] + edge.cost;
        updated = true;
    }
}

 

쉽게 말해, 위 코드를 아래처럼 변경해야 한다는 소리다.

for (Edge edge : edgeList) {
    if (dist[edge.to] > dist[edge.from] + edge.cost) {
        dist[edge.to] = dist[edge.from] + edge.cost;
        updated = true;
    }
}

 

 

모든 간선을 검사해야하기 때문에, INF가 오버플로우되어 -INF가 되는 것을 방지하기 위해 최대값을 조금 조정해주는 것이 필요하다.

 

모든 설명을 정리한 전체 코드는 아래와 같다.

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static class Edge {
        int from, to, cost;

        private Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }

    private static ArrayList<Edge> edgeList = new ArrayList<>();
    private static int[] dist;
    static final int INF = 99999999;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int TC = Integer.parseInt(br.readLine());

        StringTokenizer st;
        for (int i = 0; i < TC; i++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            dist = new int[N + 1];
            Arrays.fill(dist, INF);
            edgeList.clear();

            for (int j = 0; j < M; j++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());
                edgeList.add(new Edge(S, E, T));
                edgeList.add(new Edge(E, S, T));
            }
            for (int j = 0; j < W; j++) {
                st = new StringTokenizer(br.readLine());
                int S = Integer.parseInt(st.nextToken());
                int E = Integer.parseInt(st.nextToken());
                int T = Integer.parseInt(st.nextToken());
                edgeList.add(new Edge(S, E, -T));
            }

            if (bellmanFord(1, N)) {
                bw.write("YES\n");
            } else {
                bw.write("NO\n");
            }
        }

        bw.flush();
        bw.close();
    }

    private static boolean bellmanFord(int start, int N) {
        dist[start] = 0;

        for (int i = 1; i < N; i++) {
            for (Edge edge : edgeList) {
                if (dist[edge.to] > dist[edge.from] + edge.cost) {
                    dist[edge.to] = dist[edge.from] + edge.cost;
                }
            }
        }

        for (Edge edge : edgeList) {
            if (dist[edge.to] > dist[edge.from] + edge.cost) {
                return true;
            }
        }

        return false;
    }
}