b.11657 타임머신

 

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

 

 

 

📌 자바(Java)로 푸는 타임머신 문제 - 백준 11657 ⏳

 

🔎 문제 개요

 

백준 11657번 - 타임머신 문제입니다.

N개의 도시와 M개의 버스 노선이 주어질 때,

“1번 도시에서 다른 모든 도시로 가는 최단 시간” 을 구하는 문제입니다.

🕰 단, 음수 가중치(시간이 감소하는 경우)도 존재할 수 있으며, 음수 사이클 여부를 판별해야 합니다.

 

---

💡 예제 입력

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

💡 예제 출력

4
3
-1

➡ 1번 도시에서 각각 2번, 3번으로 가는 최단 거리 출력 (도달 불가능 시 -1)

 

---

🛠 알고리즘 접근 방식

 

이 문제를 해결하기 위해 벨만-포드 알고리즘(Bellman-Ford Algorithm) 을 사용합니다.

 

✏️ 주요 고려 사항

 

✔ 다익스트라 알고리즘을 사용할 수 없는 이유 → 음수 가중치가 존재

✔ 벨만-포드 알고리즘을 사용하여 최단 경로 계산 (O(NM))

✔ N-1번 반복하여 모든 노드의 최단 거리를 갱신

✔ N번째에도 값이 갱신되면, 음수 사이클이 존재하는 것

 

---

🔹 Java 코드 해설

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class b11657 {

    static class Node {
        int start, end, time;

        public Node(int start, int end, int time) {
            this.start = start;
            this.end = end;
            this.time = time;
        }
    }

    static int N, M;
    static ArrayList<Node> edges;
    static long[] dist; // long 타입 사용 (오버플로우 방지)
    static final long INF = Long.MAX_VALUE;

    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());

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

        // 간선 정보 입력
        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());
            edges.add(new Node(a, b, c));
        }

        // 벨만-포드 수행
        if (bellmanFord()) {
            System.out.println("-1"); // 음수 사이클 존재 시 -1 출력
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= N; i++) { // 1번 도시 제외 출력
                if (dist[i] == INF) {
                    sb.append("-1\n"); // 도달할 수 없는 경우 -1 출력
                } else {
                    sb.append(dist[i]).append("\n");
                }
            }
            System.out.println(sb);
        }
    }

    private static boolean bellmanFord() {
        boolean hasCycle = false;

        // N-1번 반복 (최단 거리 갱신)
        for (int i = 1; i < N; i++) {
            for (Node edge : edges) {
                if (dist[edge.start] != INF && dist[edge.end] > dist[edge.start] + edge.time) {
                    dist[edge.end] = dist[edge.start] + edge.time;
                }
            }
        }

        // 음수 사이클 체크 (N번째 갱신 시 값이 변하면 사이클 존재)
        for (Node edge : edges) {
            if (dist[edge.start] != INF && dist[edge.end] > dist[edge.start] + edge.time) {
                hasCycle = true;
                break;
            }
        }

        return hasCycle;
    }
}

 

 

---

🔍 코드 설명

 

📌 1. 그래프 입력 및 초기화

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

✔ 최단 거리 배열(dist[])을 INF로 초기화

✔ 1번 도시에서 출발하므로 dist[1] = 0 설정

 

---

📌 2. 벨만-포드 알고리즘 수행

for (int i = 1; i < N; i++) { // N-1번 반복
    for (Node edge : edges) {
        if (dist[edge.start] != INF && dist[edge.end] > dist[edge.start] + edge.time) {
            dist[edge.end] = dist[edge.start] + edge.time;
        }
    }
}

✔ 모든 간선을 확인하며 N-1번 동안 최단 거리 갱신

✔ 현재 간선을 통해 더 짧은 거리가 존재하면 갱신

 

---

📌 3. 음수 사이클 존재 여부 검사

for (Node edge : edges) {
    if (dist[edge.start] != INF && dist[edge.end] > dist[edge.start] + edge.time) {
        hasCycle = true;
        break;
    }
}

✔ N번째 반복에서 값이 변경되면 음수 사이클이 존재함

✔ 즉, 최단 경로를 계속 갱신할 수 있는 경우를 찾음

 

---

📌 4. 최단 거리 출력

StringBuilder sb = new StringBuilder();
for (int i = 2; i <= N; i++) {
    if (dist[i] == INF) {
        sb.append("-1\n"); // 도달할 수 없는 경우
    } else {
        sb.append(dist[i]).append("\n");
    }
}
System.out.println(sb);

✔ 1번 도시에서 2~N번 도시로의 최단 거리 출력

✔ 도달할 수 없는 경우 -1 출력

 

---

🏆 정리

 

✅ 핵심 포인트

 

✔ 벨만-포드 알고리즘을 사용하여 최단 경로 계산

✔ 음수 가중치가 존재할 수 있으므로 다익스트라가 아닌 벨만-포드 활용

✔ N번째 반복에서도 값이 갱신되면 음수 사이클 존재 판별 가능

 

🎯 이 알고리즘의 장점

 

✅ 음수 가중치가 있는 최단 경로 문제 해결 가능

✅ 음수 사이클 판별이 가능하여 무한 감소하는 경로를 감지

✅ O(NM) 복잡도로 해결 가능하여 크기가 작을 때 유용

 

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊