벨만 포드 알고리즘 feat. BOJ11657 타임머신 자바

벨만포드 알고리즘이란?

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘
특징으로는 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다 

 

벨만포드 VS 다익스트라

[다익스트라 알고리즘]

• 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
• 음수 간선이 없다면 최적의 해를 찾을 수 있다.
• 시간 복잡도가 빠르다 . 개선된 다익스트라 알고리즘도 존재하는데 이는 우선순위 큐 사용해서 구현할 수 있다

[벨만포드 알고리즘]

• (정점-1)번의 단게마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구한다
• 이때 다익스트라와의 차이점은 모든 간선을 확인한다는 것이다. 다익스트라는 방문하지 않은 노드 중에서 최단 거리가 가장 가까운 노드만을 방문한다
• 음수 간선이 있어도 최적의 해를 찾을 수 있다
• 시간 복잡도가 느리다.

그래서 이런 차이점으로 인해 모든 간선의 비용이 양수일 때는 다익스트라, 음수 간선이 포함되어 있으면 벨만 포드를 사용하면 되겠다는 결론을 지을 수 있었다.

 

BOJ 11657 - 타임머신

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

 

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

class Main {
    // 간선을 나타내는 클래스
    public static class Edge {
        int start; // 시작 노드
        int end;   // 도착 노드
        int cost;  // 가중치

        // Edge 클래스의 생성자
        public Edge(int start,int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }

    // 간선 정보 배열
    public static Edge[] nodes;
    // 노드의 수(N)과 간선의 수(M)
    public static int N, M;

    public static void main(String[] args) throws IOException {
        // 입력을 받기 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 첫 번째 줄에서 N과 M을 입력받음
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 노드의 수
        M = Integer.parseInt(st.nextToken()); // 간선의 수

        // 최단 거리 배열 (1번 노드부터 시작하므로 N+1 크기)
        long[] dist = new long[N + 1];
        // 간선 배열 초기화
        nodes = new Edge[M + 1];
        // 거리 배열을 최댓값으로 초기화 (도달 불가능한 상태를 의미)
        Arrays.fill(dist, Integer.MAX_VALUE);

        // 간선 정보 입력
        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()); // 가중치

            nodes[i] = new Edge(a, b, c); // 간선 배열에 추가
        }

        // 시작 노드의 최단 거리를 0으로 설정
        dist[1] = 0;

        // 벨만-포드 알고리즘
        for (int i = 1; i < N; i++) {
            // 모든 간선에 대해 최단 거리 갱신
            for (int j = 0; j < M; j++) {
                Edge e = nodes[j];
                // 시작 노드가 도달 가능하고, 도착 노드까지의 거리가 갱신 가능한 경우
                if (dist[e.start] != Integer.MAX_VALUE && dist[e.end] > dist[e.start] + e.cost) {
                    dist[e.end] = dist[e.start] + e.cost; // 최단 거리 갱신
                }
            }
        }

        // 음수 사이클 존재 여부 체크
        boolean cycle = false;
        for (int i = 0; i < M; i++) {
            Edge e = nodes[i];
            // 최단 거리가 또 갱신 가능하다면 음수 사이클이 존재함을 의미
            if (dist[e.start] != Integer.MAX_VALUE && dist[e.end] > dist[e.start] + e.cost) {
                cycle = true;
            }
        }

        // 결과 출력
        if (cycle) {
            System.out.println(-1); // 음수 사이클이 존재하는 경우
        } else {
            // 시작 노드(1)를 제외한 나머지 노드들의 최단 거리 출력
            for (int i = 2; i <= N; i++) {
                if (dist[i] == Integer.MAX_VALUE) {
                    System.out.println(-1); // 도달 불가능한 노드
                } else {
                    System.out.println(dist[i]); // 최단 거리 출력
                }
            }
        }
    }
}

코드 설명 추가

1. 입력 처리
   • BufferedReader와 StringTokenizer를 사용하여 입력을 받습니다.
   • 첫 줄에서 노드의 수(N)와 간선의 수(M)를 입력받습니다.
2. 간선 정보 입력
   • for 루프를 통해 M개의 간선 정보를 입력받고, nodes 배열에 저장합니다.
3. 거리 배열 초기화
   • dist 배열은 노드 수보다 1 크게 설정하여 1번 노드부터 시작할 수 있도록 하였습니다.
   • Arrays.fill() 메서드를 사용하여 배열을 Integer.MAX_VALUE로 초기화하여 초기 상태에서 도달할 수 없음을 나타냅니다.
   • 1번 노드에서 시작하므로 dist[1]을 0으로 설정합니다.
4. 벨만-포드 알고리즘 수행
   • N-1번의 루프를 돌며 모든 간선에 대해 최단 거리를 갱신합니다. 이는 N번째에 최단 거리가 더 갱신된다면 음수 사이클이 존재함을 확인하기 위함입니다.
5. 음수 사이클 검사
   • 한 번 더 모든 간선을 순회하여 최단 거리가 갱신되는 경우 음수 사이클이 존재함을 의미합니다. 이 경우 cycle 플래그를 true로 설정합니다.
6. 결과 출력
   • 음수 사이클이 존재하는 경우 -1을 출력합니다.
   • 음수 사이클이 존재하지 않는 경우, 1번 노드를 제외한 나머지 노드의 최단 거리를 출력합니다. 도달할 수 없는 경우 -1을 출력합니다.