[BOJ/Java] 11657. 타임머신

📌 [BOJ/Java] 11657. 타임머신

• 문제 링크

---

💡 문제 해석

한 도시에서 다른 도시로 이동하는 버스 노선이 주어진다.
일부 노선에는 음의 가중치(시간)가 존재하며, 음수 사이클이 발생할 수도 있다.

🔹 주어진 정보

• N: 도시의 개수 (노드)
• M: 버스 노선의 개수 (간선)
• A B C: A번 도시에서 B번 도시로 가는 시간이 C(양수 또는 음수)

✅ 목표:
1️⃣ 1번 도시에서 모든 도시로 가는 최단 시간을 구한다.
2️⃣ 음수 사이클이 존재하는지 판별한다.

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

🚀 1 → 2 → 3 → 1로 돌아오면 음수 사이클 발생!

---

📝 풀이 과정

1️⃣ 벨만-포드 (Bellman-Ford) 알고리즘 사용

✔ 음수 가중치가 존재할 수 있기 때문에 다익스트라가 아닌 벨만-포드 알고리즘을 사용
✔ N-1번 모든 간선을 확인하며 최단 경로 갱신
✔ N번째 갱신에서 값이 줄어들면 음수 사이클 존재!

2️⃣ 알고리즘 진행 방식

✅ 모든 최단 경로를 **무한대(INF)**로 초기화
✅ N-1번 동안 모든 간선을 순회하면서 거리 갱신
✅ N번째 반복에서 갱신이 발생하면 음수 사이클 존재!

---

💻 코드 (Java)

 

import java.util.*;

public class Main {
    static final long INF = Long.MAX_VALUE;
    static int N, M;
    static List<Edge> edges;
    static long[] dist;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        edges = new ArrayList<>();
        dist = new long[N + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0; // 시작점 설정

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            edges.add(new Edge(u, v, w));
        }

        if (bellmanFord()) {
            System.out.println("-1"); // 음수 사이클 존재
        } else {
            for (int i = 2; i <= N; i++) {
                System.out.println(dist[i] == INF ? "-1" : dist[i]);
            }
        }
    }

    static boolean bellmanFord() {
        boolean updated = false;
        
        for (int i = 1; i < N; i++) { // N-1번 반복
            updated = false;
            for (Edge edge : edges) {
                if (dist[edge.u] != INF && dist[edge.v] > dist[edge.u] + edge.w) {
                    dist[edge.v] = dist[edge.u] + edge.w;
                    updated = true;
                }
            }
            if (!updated) break;
        }

        // N번째 반복에서 갱신 발생하면 음수 사이클 존재
        for (Edge edge : edges) {
            if (dist[edge.u] != INF && dist[edge.v] > dist[edge.u] + edge.w) {
                return true;
            }
        }
        return false;
    }

    static class Edge {
        int u, v, w;
        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

---

⏱ 시간 복잡도 분석

• 벨만-포드 알고리즘: O(N × M)
• N ≤ 500, M ≤ 6000이므로 최악의 경우 500 × 6000 = 3,000,000 연산 (가능)

---

🧐 느낀 점

🌟 벨만-포드를 활용한 대표적인 문제였다.
➡️ 음수 가중치가 포함된 경우는 다익스트라 대신 벨만-포드 사용!
➡️ N번째 갱신 여부를 체크하면 음수 사이클 판별이 가능하다.

🔍 디테일한 부분에서 실수하기 쉬웠다.
✅ dist 배열을 Long 타입으로 선언해야 오버플로우 방지 가능!
✅ 시작점(1번 도시)을 0으로 초기화하는 것 잊지 않기
✅ 음수 사이클이 존재하면 -1을 바로 출력하고 종료해야 한다.

🚀 음수 가중치 그래프 문제를 연습하는 데 아주 좋은 문제였다! 😊