BOJ_11657 : 타임머신

👉 문제링크

---

---

🔸 문제 분석 🔸

• N개의 도시와 M개의 버스가 주어진다. 1번 도시에서 나머지 도시로 가는 최단 시간을 출력한다.
• 버스는 시작 도시, 도착 도시, 이동 시간으로 이루어져 있다.
• 이동 시간은 정수로 주어진다.

🔸 문제 풀이 🔸

• 그래프에서 최단 거리를 구하는 문제이고, 음의 가중치가 있으므로 벨만 포드 알고리즘을 이용한다.
• N번 마다 M개의 간선을 모두 검사하므로, 시간 복잡도는 O(NM)이다.
• 이동 시간의 최대값은 499 * 10,000 으로, 약 5,000,000 까지 커지므로 int형으로 처리 된다.
  (노드가 일렬로 연결되어 있고, 에지의 최대 값인 10,000으로만 연결 된 경우)
• 이동 시간의 최소값은 500 * 6,000 * -10,000 으로, -3,000,000,000(-30억) 까지 커지므로 int형의 범위를 벗어나기 때문에 long의 자료형이 필요하다.
  (음수 사이클이 있어서 N*M 동안 가중치의 최소값인 -10,000이 누적된 경우)

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long[] dist = new long[N + 1];
        Edge[] edges = new Edge[M];

        for (int i = 1; i <= N; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            edges[i] = new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // Bellman-ford-moore
        dist[1] = 0;
        boolean minusCircle = false;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < M; j++) {
                if (dist[edges[j].start] == Integer.MAX_VALUE) // 엣지 시작 노드가 방문 전(무한대)이면 통과
                    continue;
                if (dist[edges[j].end] > dist[edges[j].start] + edges[j].cost) {
                    dist[edges[j].end] = dist[edges[j].start] + edges[j].cost;
                    if (i == N) {
                        minusCircle = true;
                    }
                }
            }
        }

        // Output
        if (minusCircle)
            bw.write("-1");
        else {
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= N; i++) {
                if (dist[i] == Integer.MAX_VALUE)
                    sb.append("-1");
                else
                    sb.append(dist[i]);
                sb.append('\n');
            }
            bw.write(sb.toString().stripTrailing());
        }
        bw.flush();
    }

    private static class Edge {
        int start, end, cost;

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

🔸 코드 해석 🔸

• 간선 표현을 위해 시작 노드, 도착 노드, 가중치를 저장하는 Edge 클래스를 정의해 사용했다.
• 벨만-포드 알고리즘을 구현해서 음수 사이클이 있으면 -1, 없다면 최단 거리를 출력했다.

---

🔸 end 🔸

• 벨만-포드 알고리즘을 복습할 수 있는 기회가 되어서 포스팅으로 정리했다.
• 최단 거리의 최대 최소값을 계산해보지 않아서 오버플로우로 '출력 초과'가 떠서 틀렸다.
  • 처음엔 끝에 공백(' ')이 들어가서 틀렸나, strip을 넣어봤지만 여전했다.
  • 질문하기를 보니, 최솟값이 음수 사이클을 타면 -30억까지 갈 수 있어서 long을 사용해야 했다.
  • 최대 최소 엣지케이스를 꼭 따져보는 습관을 들여야 겠다.