[Algorithm] 백준 벨만포드 문제 - 타임머신(11657) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 벨만포드 문제 - 타임머신 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
    static final int INF = Integer.MAX_VALUE;
    static long[] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken()); // 정점 개수
        int m = parseInt(st.nextToken()); // 간선 개수
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int e = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());
            
            graph.get(e).add(new Edge(v, w)); // 그래프에 엣지 추가하기
        }
        
        dist = new long[n + 1]; // 정점 개수로 dist 초기화 노드 1번에서 각 노드 출발
        Arrays.fill(dist, INF);
        dist[1] = 0; // 시작노드인 1번은 = 0

        for (int k = 0; k < n - 1; k++) { // 벨만 포드 알고리즘은 k - 1번 반복
            for (int i = 1; i <= n; i++) { // 정점 개수
                ArrayList<Edge> edges = graph.get(i);

                for (Edge edge : edges) {
                    if (dist[i] != INF && dist[edge.v] > dist[i] + edge.w) {
                        dist[edge.v] = dist[i] + edge.w; // 출발 정점에서 도착 정점까지의 거리가, 이전의 값보다 작다면 업데이트
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) { // 음수 사이클이 존재하는지 판단
            ArrayList<Edge> edges = graph.get(i);

            for (Edge edge : edges) {
                if (dist[i] != INF && dist[edge.v] > dist[i] + edge.w) { // 만약 음수 사이클로 인해 이전 값이 줄어든다면 무한 사이클 가능
                    sb.append(-1).append("\n");
                    System.out.print(sb);
                    return;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (dist[i] == INF) sb.append(-1).append("\n"); // 갈 수 없는 곳이라면
            else sb.append(dist[i]).append("\n");
        }

        System.out.print(sb);
    }
    
    static class Edge {
        int v; // 도착 정점
        int w; // 가중치
        
        Edge (int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
}

 

2. 벨만포드 알고리즘

 

벨만포드 알고리즘은 그래프 최단 경로를 구하는 알고리즘으로, 하나의 정점에서 출발하는 최단 거리를 구하는 문제입니다. 

음수 가중치를 허용하는 것이 특징입니다.

 

벨만 포드 알고리즘은 다음의 절차로 이루어집니다.

• 간선 m개를 하나씩 모두 탐색
• dist[도착 정점] = min(dist[도착 정점], dist[출발지 정점] + cost(도착지 정점으로 가는 간선의 가중치))
• 노드 개수의 n - 1개 만큼 이를 반복하여 특정 정점에서 각 노드로의 이동거리를 업데이트 진행

 

이를 그림의 예시로 설명하면 다음과 같습니다.

 

 

해당 그래프와 간선은 다음과 같이 주어졌다고 가정하겠습니다.

 

초기 dist배열은 1번 노드에서, 각 노드로의 최단 거리를 담고 있습니다. 1번 노드에서 1번 노드의 이동은 0으로 초기화하고, 나머지 노드로의 이동은 아직 간선으로 이동하지 않았으므로 무한대로 초기화합니다.

 

1번 노드에서 3번 노드로 연결된 간선을 통해 dist가 업데이트될 수 있습니다. 이때 조건은 다음과 같습니다.

 

if (dist[i] != INF && dist[edge.v] > dist[i] + edge.w) {
    dist[edge.v] = dist[i] + edge.w; // 출발 정점에서 도착 정점까지의 거리가, 이전의 값보다 작다면 업데이트
}

 

i는 이동을 시작하는 곳의 노드 번호이고, edge.v는 도착하려는 곳의 정점입니다.

dist[i], 즉 1번 노드의 dist[1] = 0 이고, 이동하려는 3번 노드의 거리는 무한대인데, dist[i] + edge.w가 1이므로 3번 노드의 거리를 업데이트합니다.

수식: dist[edge.v] > dist[i] + edge.w          =>           dist[3] > dist[1] + 1                  =>        ∞ > 1      =>    dist[3] = 1

 

다음은 2번 노드에서 4번 노드로 이동하는 간선입니다.

이때, dist[2] = ∞입니다. 따라서, 해당 간선은 dist[i] != INF라는 조건에 위배되어 실행되지 않고 넘어갑니다.

 

 

다음은 3번 노드에서 2번 노드로 이동하는 간선의 차례입니다.

dist[3] = 1이므로 dist[3] != INF를 만족합니다.

    dist[2] > dist[3] + 1 

 = ∞ > 2

=> dist[2] = 2를 만족하게 됩니다.

 

이렇게 종료된다면, 2 -> 4로 이동하는 것은 여전히 무한대로 남아있습니다.

앞 서, n - 1번을 반복하는 이유가 이러한 반례가 존재하기 때문입니다.

따라서, n - 1번 반복을 하게 된다면, 2번 노드가 현재 1로 업데이트 되어 있으므로 4번 노드까지의 거리를 업데이트할 수 있습니다.

 

 

3. 벨만포드 알고리즘 음수 간선

 

앞서 양수로 움직이는 벨만포드 알고리즘을 확인할 수 있었습니다. 벨만포드 알고리즘은 음수 간선을 적용할 수 있다는 점에서 다익스트라 알고리즘과 비교할 수 있습니다.

 

음수 간선이 적용된다면, 벨만포드 알고리즘은 어떻게 처리가 될까요?

 

이번 예시는

1 -> 2 : 1

2 -> 3 : 1

3 -> 1 : -1

로 처리되는 그래프를 예시로 확인해 보겠습니다.

 

이 그래프는 1 -> 2 -> 3 -> 1로 이어지는 사이클을 형성하고 있습니다.

벨만포드 알고리즘으로 각 간선을 적용하여 n - 1번 반복하며 값을 업데이트하면 다음과 같습니다.

1 -> 2 이동 거리 업데이트 

 

2 -> 3 이동 거리 업데이트

 

 

3 -> 1 거리 업데이트.

 

 

이렇게까지 종료를 하면, 올바른 답을 구하지 못할 수 있습니다.

이 예시에서는 이렇게 종료하더라도, 문제가 발생하지 않습니다.

하지만, 만약 음수 사이클이 존재하여 값이 무한대로 감소하게 된다면, 최단 거리를 구할 수 없게 됩니다.

 

4. 벨만포드로 음수 사이클 판단하기

 

예시를 조금 수정하여, 음수 사이클이 적용되는 예시를 만들어 보았습니다.

 

간선은

1 -> 2 : 1

2 -> 3 : 1

3 -> 1: -10으로 구성됩니다.

 

마찬가지로 각 간선으로 거리를 구하면 다음의 절차를 따릅니다.

 

 

1 -> 2 거리 업데이트 1

 

 

2 -> 3 거리 업데이트 2

 

3 -> 1 거리 업데이트 -8 

 

여기서 벨만포드 알고리즘은, 간선을 업데이트하는 방식을 한 번 더 적용하여, 해당 간선이 음수 사이클을 형성하고 있는지 판단할 수 있습니다.

지금 1 -> 2 -> 3 -> 1까지 거치는 최종 거리는 -8입니다.

만약 한 번 더 이동을 하게 된다면 1- > 2 -> 3 -> 1 -> 2 -> 3 -> 1 는 -16이 되게 됩니다.

즉, 무한번 사이클을 회전하게 된다면 그 값이 무한정 감소하게 되는 것입니다.

 

따라서 벨만포드 알고리즘은 다음의 절차로 정리할 수 있습니다

 

• 모든 노드의 거리를 무한대로 설정하고 시작 노드의 거리만 0으로 설정합니다.
• 모든 간선에 대해, 만약 시작 노드에서 해당 간선의 시작점까지의 현재 거리와 간선의 가중치의 합이 간선의 끝점까지의 현재 거리보다 작다면, 간선의 끝점까지의 거리를 업데이트합니다. 이 단계를 노드 수 - 1번 반복합니다.
• 모든 간선을 다시 한 번 검사하여, 만약 위의 업데이트를 계속할 수 있다면 이는 음의 사이클이 존재함을 의미합니다.

 

5. 코드로 정리하기

 

for (int i = 1; i <= n; i++) { // 음수 사이클이 존재하는지 판단
    ArrayList<Edge> edges = graph.get(i);

    for (Edge edge : edges) {
        if (dist[i] != INF && dist[edge.v] > dist[i] + edge.w) { // 만약 음수 사이클로 인해 이전 값이 줄어든다면 무한 사이클 가능
            sb.append(-1).append("\n");
            System.out.print(sb);
            return;
        }
    }
}

•  

앞 서, 음의 사이클이 존재하는지 여부는 이처럼 간선을 한 번더 탐색하여, 값이 업데이트되는 경우가 존재하는지 판단합니다.

dist[edge.v] > dist[i] + edge.w 가 실행된다는 것은, 이전에 업데이트한 값보다 더 작은 값이 생성된다는 의미이므로, 음의 사이클이 발생했다고 판단할 수 있습니다.

 

이상으로 벨만포드 알고리즘으로 해결할 수 있는 타임머신 문제 풀이를 마치도록 하겠습니다. 감사합니다!