[BOJ/GoldIV] 11657. 타임머신 - JAVA 자바

11657번: 타임머신

• 244ms
• 벨만 포드 알고리즘

특정 노드(1번 노드)에서 모든 노드로 가는 가장 빠른 시간을 순서대로 출력하는 문제로 최단 경로를 계산하는 문제이다. 그리고 이 문제에서는 가중치가 음수의 값을 가지므로 다익스트라가 아닌 벨만 포드 알고리즘으로 최단 경로를 계산한다.

 

음의 가중치 순환으로 시간을 무한히 오래 전으로 되돌릴 수 있으면 -1 출력해야 하므로 전체 간선을 확인하며 최단 거리 테이블 d 를 갱신한 뒤, 한 번 더 간선을 확인하며 최단 거리 테이블이 새로 갱신된다면 음의 간선 순환이 존재하므로 true 를 리턴해준다.

 

시간복잡도는 O(NM) 이 된다.

INF 는 1e9(10억)일 때, 출력초과가 떠 1e10 으로 바꿔줌

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

public class Main {
    static int n, m, INF = (int) 1e10;
    static ArrayList<Edge> graph = new ArrayList<>();;
    static long[] d;

    static class Edge {
        int v;
        int w;
        int cost;

        public Edge(int start, int end, int cost) {
            this.v = start;
            this.w = end;
            this.cost = cost;
        }
    }

    public static boolean BellmanFord(int start) {
        d[start] = 0;

        // 정점의 개수만큼 반복
        for (int i = 0; i < n; i++) {
            // 간선의 개수만큼 반복
            for (int j = 0; j < m; j++) {
                Edge edge = graph.get(j);

                // 현재 간선의 들어오는 정점에 대해 비교
                if (d[edge.v] != INF && d[edge.w] > d[edge.v] + edge.cost)
                    d[edge.w] = d[edge.v] + edge.cost;
            }
        }

        // 음의 가중치 확인
        for (int i = 0; i < m; i++) {
            Edge edge = graph.get(i); // 현재 간선

            // 현재 간선의 들어오는 정점에 대해 비교 => 더 작은 값이 생기면 음수 사이클 존재
            if (d[edge.v] != INF && d[edge.w] > d[edge.v] + edge.cost)
                return false;
        }

        return true;

    }

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

        d = new long[n + 1];
        Arrays.fill(d, INF);

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            graph.add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
                    Integer.parseInt(st.nextToken())));
        }

        boolean flag = BellmanFord(1);

        for (int i = 2; i <= n; i++) {
            if (flag) {
                if (d[i] == INF) sb.append(-1);
                else sb.append(d[i]);
            } else {
                sb.append(-1).append('\n');
                break;
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }
}