[백준] 11657번 타임머신 (JAVA)

문제

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

11657번: 타임머신

 

설명

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구해야 한다.
시간 C가 양수가 아닌 경우가 있다.
C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
만약 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.

음의 가중치가 있는 그래프에서 최단 경로를 구하는 방법으로는 벨만-포드 알고리즘이 있다.

먼저 시작도시, 도착도시, 이동 시간을 저장할 Bus 클래스를 만들고 리스트를 만들어 연결관계를 저장한다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 나타내는 minTime[] 배열을 만든다.

 

getMinTime() 함수에서는 1번 도시에서부터 (N - 1)개의 도시까지의 최소 소요 시간을 구한다.

연결관계를 저장한 buses의 원소를 하나하나 조사해서 해당 출발지에 해당하는 minTime 값이 존재하고 해당 도착지에 해당하는 minTime 값보다 해당 출발지에 해당하는 minTime 값과 소요시간을 더한 값이 작다면 최소 시간을 갱신한다. 

N번째 과정에도 갱신되는 값이 있다면 음의 사이클이 존재한다는 의미이므로 -1을 출력한다.

마지막으로, 모든 과정이 끝난 후에도 경로가 존재하지 않는 경우에 -1을 출력한다.

class Bus {
    int start;
    int dest;
    int time;

    public Bus(int start, int dest, int time) {
        this.start = start;
        this.dest = dest;
        this.time = time;
    }
}

void getMinTime() {
    for (int i = 1; i <= N; i++) {
        for (Bus bus : buses) {
            if ((minTime[bus.start] != Long.MAX_VALUE)
                    && (minTime[bus.start] + bus.time < minTime[bus.dest])) {
                // N번째 과정에도 값이 변한다면 음의 사이클이 존재한다는 의미이다
                if (i == N) {
                    System.out.println(-1);
                    return;
                }
                else {
                    minTime[bus.dest] = minTime[bus.start] + bus.time;
                }
            }
        }
    }

    for (int i = 2; i <= N; i++) {
        if (minTime[i] == Long.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(minTime[i]);
    }
}

 

전체 코드

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

public class Main {

    static int N, M;
    static ArrayList<Bus> buses;
    static long[] minTime;  // 음의 간선이 클 경우 underflow가 발생하게 되어 출력초과가 나오는 경우가 있기 때문에 long[]으로 선언한다

    static class Bus {
        int start;
        int dest;
        int time;

        public Bus(int start, int dest, int time) {
            this.start = start;
            this.dest = dest;
            this.time = time;
        }
    }

    static void getMinTime() {
        for (int i = 1; i <= N; i++) {
            for (Bus bus : buses) {
                if ((minTime[bus.start] != Long.MAX_VALUE)
                        && (minTime[bus.start] + bus.time < minTime[bus.dest])) {
                    // N번째 과정에도 값이 변한다면 음의 사이클이 존재한다는 의미이다
                    if (i == N) {
                        System.out.println(-1);
                        return;
                    }
                    else {
                        minTime[bus.dest] = minTime[bus.start] + bus.time;
                    }
                }
            }
        }

        for (int i = 2; i <= N; i++) {
            if (minTime[i] == Long.MAX_VALUE)
                System.out.println(-1);
            else
                System.out.println(minTime[i]);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        buses = new ArrayList<>();

        minTime = new long[N + 1];
        for (int i = 1; i <= N; i++) {
            if (i == 1)
                minTime[i] = 0;
            else
                minTime[i] = Long.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());

            buses.add(new Bus(A, B, C));
        }

        getMinTime();
    }
}