[백준-java] 골드 4 타임머신

알고리즘 : 벨만 포드 알고리즘

다익스트라 알고리즘과 달리 음의 가중치인 경우에 최단경로 구하기가 가능하다.
하지만 다익스트라 알고리즘에 비해서 모든 간선을 다 확인하므로 O(V * E)로 시간복잡도가 느리다.
또한 음의 순환의 확인이 가능하다.

음의 순환이 존재하면 최단경로는 구할 수 없다.

---

문제

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

내 풀이

기본적인 벨만포드 알고리즘으로 풀었다.
풀다보면 38프로에서 출력초과가 뜨는 경우가 있는데

이 조건에서 n= 500,m = 6000인 경우 모든 간선이 -10000 일 경우 최단경로 값이 -30억이 나올 수 있기에

Int오버플로우가 발생하는 경우 일 것이다. 이는 dist 배열을 Long 타입으로 선언하여 해결 할 수있다.

package com.example;

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

class Node {
    int dest, cost;
    public Node(int dest, int cost) {
        this.dest = dest;
        this.cost = cost;
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 초기화
        ArrayList<Node>[] adjList = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int source = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            adjList[source].add(new Node(dest, cost));
        }

        long[] dist = new long[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        // v-1 번 반복해서 간선 업데이트
        for (int i = 0; i < n - 1; i++) {
            for (int j = 1; j <= n; j++) {
                for (Node node : adjList[j]) {
                    if (dist[j] != Integer.MAX_VALUE && dist[node.dest] > dist[j] + node.cost) {
                        dist[node.dest] = dist[j] + node.cost;
                    }
                }
            }
        }

        // 한번 더 반복해서 값이 변했으면 -1 즉 음의 사이클 존재
        boolean hasNegativeCycle = false;
        outer:
        for (int j = 1; j <= n; j++) {
            for (Node node : adjList[j]) {
                if (dist[j] != Integer.MAX_VALUE && dist[node.dest] > dist[j] + node.cost) {
                    System.out.println("-1");
                    hasNegativeCycle = true;
                    break outer;  // 음의 사이클 발견 시 바로 종료
                }
            }
        }

        // 음의 사이클이 없으면 결과 출력
        if (!hasNegativeCycle) {
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= n; i++) {
                if (dist[i] == Integer.MAX_VALUE) {
                    sb.append("-1\n");
                } else {
                    sb.append(dist[i]).append("\n");
                }
            }
            System.out.print(sb);
        }
    }
}