[BOJ] 타임머신 - 백준 11657 (JAVA) - 벨만-포드

📌 벨만-포드

벨만-포드(bellman-ford-moore) 알고리즘은 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색하는 알고리즘이다.

다익스트라와는 다르게 음수 가중치 에지가 있어도 수행 가능하며, 주로 전체 그래프에서 음수 사이클 존재 여부를 판단하는 문제로 나온다.

 

 

1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화

 

최단 경로 배열은 출발 노드는 0, 나머지는 무한대로 초기화한다. (구현할 때는 Integer.MAX_VALUE로 초기화)

Edge 클래스에 출발노드, 도착노드, 가중치를 담고 Edge 클래스 리스트 또는 배열을 구현한다.  

 

2. 모든 에지를 확인해 최단 경로 배열 업데이트, (노드 개수 - 1) 번 반복

 

최단 경로 배열을 dist[] 라고 하면, dist[출발노드] 가 무한대가 아니며, dist[도착노드] > dist[출발노드] + 해당 출발-도착 노드 가중치 일 때 dist[도착노드] 를 부등호 오른쪽과 같이 업데이트 한다. 

 

dist[edge.start] != Integer.MAX_VALUE && dis[edge.end] > dist[edge.start] + edge.value

 

i 번 반복했을 때의 정답 배열의 의미는 에지를 i번 이하로 사용해서 출발노드에서 다른 노드까지 갈 수 있는 최단거리이다.

 

음수 사이클이 없을 때 특정 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수가 (노드 개수 - 1)이기 때문에  (노드 개수 - 1)만큼 반복하는 것이다. 

 

음수 사이클이 존재하지 않는다면 (노드 개수 - 1) 번 반복 후에는 출발 노드와 다른 노드 간에 최단거리를 구할 수 있다.

 

만약 음수 사이클이 존재한다면 한 번 더 반복했을 때 업데이트되는 값이 생기기 때문에 업데이트 여부로 음수 사이클 여부를 판단할 수 있다.

🔒 타임머신 - 백준 11657

https://www.acmicpc.net/problem/11657

 

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는 데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

🔑 핵심 아이디어

벨만-포드 알고리즘 사용

🔎 주의할 점

distance 배열을 int 배열로 선언하면 출력초과로 나온다.

 

벨만 포드는 전체 과정을 에지의 수(M)만큼 돌리기 때문에, 음수 사이클의 절댓값의 최대 길이가 6천만(M<=6000, |C|<=10,000)이라면 그 과정을 다시 N번 반복하면서 N을 곱한 것만큼 절댓값을 키우게 된다. (N ≤ 500 -> 21억 int 범위 넘음)

따라서 distance 배열을 long 타입으로 해야 한다.

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        Edge[] edges = new Edge[M];

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            edges[i] = new Edge(u,v,w);
        }

        long[] distance = new long[N+1];
        for (int i = 0; i <= N; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        // 벨만-포드 알고리즘
        distance[1] = 0; // 1번 도시에 출발
        for (int i = 1; i < N; i++) { // N-1번 업데이트
            for (int j = 0; j < M; j++) { // 모든 에지 확인
                Edge edge = edges[j];
                if(distance[edge.start] != Integer.MAX_VALUE){ // "<" 도 맞음
                    if(distance[edge.end] > distance[edge.start]+edge.value){
                        distance[edge.end] = distance[edge.start]+edge.value;
                    }
                }
            }
        }
        // 음수 사이클 확인
        boolean isCycle = false;
        for (int i = 0; i < M; i++) { 
            Edge edge = edges[i];
            if(distance[edge.start] != Integer.MAX_VALUE){
                if(distance[edge.end] > distance[edge.start]+edge.value){
                    isCycle = true;
                }
            }
        }
        if(!isCycle){
            for (int i = 2; i <=N; i++) {
                if(distance[i] == Integer.MAX_VALUE) // 1번에서 도달할 수 없는 노드
                    System.out.println(-1);
                else
                    System.out.println(distance[i]);
            }
        }else{
            System.out.println(-1);
        }
    }
}
class Edge{
    int start, end, value;

    public Edge(int start, int end, int value) {
        this.start = start;
        this.end = end;
        this.value = value;
    }
}

 

 

---

코테 정리 깃허브 링크

GitHub - HyperAlgorithmStudy/BaekJoon: Do it! 알고리즘 코딩 테스트 스터디

참고: Do it! 알고리즘 코딩 테스트: 자바 편 - 김종관