[백준 11657 : JAVA] 타임머신 / 벨만-포드

개요

 

문제를 읽어보면 그래프의 가중치가 음수인 경우가 있고, 한 노드 ▶ 모든 노드의 최단경로를 구하는 것이다.

그리고 음의 사이클이 존재하면 -1을 출력하고

만약 경로가 존재하지 않으면 -1을 출력한다.

 

위의 조건들을 살펴보면, 가중치가 음수이므로 다익스트라는 사용할 수 없다.

한 노드 ▶ 모든 노드 이므로 플로이드 와샬 말고 벨만 포드이면 충분할 것 같다.

음의 사이클 유무를 확인해야 하므로 벨만 포드이면 충분할 것 같다.

 

만약 음의 사이클이 무엇인지 헷갈린다면 아래의 문제와 풀이를 먼저 공부하고 이 문제를 푼다면 도움이 될 것이다.

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

1865번: 웜홀

2020/02/12 - [알고리즘/백준] - [백준 1865 : JAVA] 웜홀/ 벨만-포드

[백준 1865 : JAVA] 웜홀/ 벨만-포드

 

문제

 

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

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

 

입력

 

풀이

 

총 v개의 노드가 있고 e개의 간선이 있다면,

 

|v - 1|번 e개의 간선에 대해 dist[]를 갱신해준다.

 

그러고 나서 1번 e개의 간선에 대해 dist[]를 갱신하려고 할 때 갱신이 된다면 음의 사이클이 있다는 뜻이다.

 

만약 dist[]의 값이 INF 라면 해당 경로가 없다는 것을 의미한다.

 

코드

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

class Bus{
    // 시작점, 도착점, 걸리는 시간
    int start, end, weight;

    public Bus(int start, int end, int weight){
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 500 * 100_000;
    static int n, m;
    static int dist[];
    static Bus busArr[];

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

        busArr = new Bus[m + 1];
        dist = new int[n + 1];
        // 최단거리 배열 무한대로 초기화
        for(int i = 1 ; i <= n; i++) dist[i] = INF;

        // 입력값 초기화
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());

            busArr[i] = new Bus(start, end, time);
        }
        // 결과 출력을 위한 객체
        StringBuilder sb = new StringBuilder();

        // 음의 cycle이 없는 경우
        if(bellmanFord()){
            for(int i = 2; i <= n; i++){
                sb.append(dist[i] == INF ? "-1\n" : dist[i] + "\n");
            }
        // 음의 cycle이 있는 경우
        }else{
            sb.append("-1\n");
        }

        bw.write(sb.toString());
        bw.close();
        br.close();
    }
    // 음의 cycle이 있다면 false리턴 없다면 true리턴
    // 벨만포드 알고리즘
    private static boolean bellmanFord() {
        // 시작점 최단거리 0 갱신
        dist[1] = 0;

        // v - 1번 수행
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                Bus bus = busArr[j];
                // 더 작은 최단거리 가 있는 경우 갱신
                if(dist[bus.start] != INF && dist[bus.end] > dist[bus.start] + bus.weight){
                    dist[bus.end] = dist[bus.start] + bus.weight;
                }
            }
        }

        // 음수 cycle 확인
        // 갱신되는게 있다면 음수 cycle이 있다는 뜻
        for(int i = 0; i < m; i++){
            Bus bus = busArr[i];

            if(dist[bus.start] != INF &&dist[bus.end] > dist[bus.start] + bus.weight) return false;
        }

        return true;
    }
}