[백준_11657] 타임머신

문제

백준 11657번
https://www.acmicpc.net/problem/11657

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

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

• 예시
  

• 1 -> 2로 갈때 시간이 4
• 1 -> 2 -> 3으로 갈 때 3 그리고 1 -> 3 으로 갈 때 3
• 1 에서 다시 1로 돌아오면 1로 이전인 0보다 큰 값이기에 이후 이동해도 더 빨리 가는 시간은 나오지 않는다.

Code

간선에 음수가 있었기 때문에 다익스트라가 아닌 벨만-포드로 풀어야 했다. 하지만, 모든 간선을 방문해야하기 때문에 다익스트라보다는 느리다!! 간선에 음수가 없다면 무조건 다.익.스.트.라!!

Java

import java.util.*;

public class Main {

    static class Edge {
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    final static int INF = 1000000000;
    static Edge[] edge;
    static long[] dist;

    public static void solution(int N, int M, int[][] data, int start) {
        edge = new Edge[M];
        for (int i = 0; i < M; i++) {
            edge[i] = new Edge(data[i][0], data[i][1], data[i][2]);
        }

        dist = new long[N + 1];  // 최단 경로 배열 초기화
        for (int i = 1; i < N + 1; i++) {
            dist[i] = INF;
        }
        dist[start] = 0;

        if (bellmanFord(N, M)) {  // 음수 사이클이 나올 경우
            System.out.println(-1);
        } else {
            for (int i = 2; i < N + 1; i++) {
                if (dist[i] == INF) {  
                // 음수 사이클은 아니지만, 갈 수 있는 방법이 없을 때
                    System.out.println(-1);
                } else {
                    System.out.println(dist[i]);
                }
            }
        }
    }

        public static boolean bellmanFord(int N, int M) {
            boolean isMinusCycle = false;
            for (int i = 0; i < N + 1; i++) {
                for (int j = 0; j < M; j++) {
                    Edge cur = edge[j];

                    if (dist[cur.from] == INF) {
                        continue;
                    }

                    if (dist[cur.to] > dist[cur.from] + cur.weight) {
                    // 현재 위치에서 다른 노드로 이동하는 거리가 더 짧을 경우
                        dist[cur.to] = dist[cur.from] + cur.weight;

                        // 음수 사이클 체크
                        if (i == N) {
                            isMinusCycle = true;
                        }
                    }
                }
            }
            return isMinusCycle;
        }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();  // 도시의 개수
        int M = sc.nextInt();  // 버스 노선의 개수

        int[][] data = new int[M][3];  // 
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < 3; j++) {
                data[i][j] = sc.nextInt();
            }
        }
        solution(N, M, data, 1);
    }     
}

• 첫 번째 예제로만 해설할 예정이고, 나머지 예제도 같은 방법으로 해결 가능!
• 먼저, data값들을 edge로 간선을 구성한다.
• 그리고 거리 배열인 dist를 만들어주고 음수사이클 체크할 boolean도 하나 만들어 준다.
• 그리고 start값은 0으로 초기화 시켜준다.

• 0번째 edge로 거리 확인
• 원래 dist가 INF 였기 때문에 더 작은 값인 4로 바꾸어 준다.

• 1번째 edge로 거리 확인
• 원래 dist가 INF 였기 때문에 더 작은 값인 3로 바꾸어 준다.

• 2번째 edge로 거리 확인
• 원래 dist가 3으로 우측 식 계산 값 또한, 3으로 변경되지 않는다.

• 3번째 edge로 거리 확인
• 원래 dist가 0으로 우측 식 계산 값 또한, 1로 좌측보다 크기 때문에 변경되지 않는다.

• 최종적으로 나온 1번 도시에 2, 3, ... N번 도시로 가는 가장 빠른 시간이다.