11657 - 타임머신 (Java)

박세건·2025년 4월 11일

11657 백준 벨만포드 타임머신

알고리즘 문제 해결

목록 보기

45/50

최단거리 구하기 + 음수 사이클 판별 문제
https://www.acmicpc.net/problem/11657

📌 문제 요약

N개의 도시와 M개의 버스(간선)가 주어짐
1번 도시에서 출발해 나머지 모든 도시까지 최단거리 구하기
조건
- 음수 사이클 존재 시 -1 출력
- 도달 불가능한 도시는 -1 출력

🧠 접근 과정

1️⃣ 첫 번째 접근 — 다익스트라 알고리즘

아이디어 : 다익스트라 + 이전 노드를 기억해서 사이클 체크 시도
문제 발생 ⚠️
- 음수 사이클은 꼭 다시 되돌아가는 경로가 아니어도 발생 가능
- 다른 경로로 인해 최단거리가 무한히 갱신될 수 있음
- 다익스트라는 음수 가중치/사이클 문제에 부적절

2️⃣ 두 번째 접근 — 다익스트라 + 유니온파인드

아이디어 : 유니온파인드로 사이클 여부 체크
문제 발생 ⚠️
- 최단거리가 다른 경로로 갱신되는 상황을 보장하지 못함
- 다익스트라 한계 그대로 노출

3️⃣ 세 번째 접근 — 벨만포드 알고리즘 (정답)

아이디어 : DP 개념 기반으로 모든 경로 탐색
핵심 동작
- N-1번 전체 간선 탐색 → 최단거리 갱신
- 이후 1번 더 탐색 시 값 갱신 → 음수 사이클 존재

💡 벨만포드 알고리즘 핵심 로직

거리 초기화

for (int i = 0; i < N + 1; i++) {
    dp[i] = Long.MAX_VALUE;
}
dp[1] = 0;

최단거리 갱신 (N-1번 반복)

for (int i = 0; i < N - 1; i++) {
    for (int j = 0; j < connInfo.size(); j++) {
        int from = connInfo.get(j)[0];
        int to = connInfo.get(j)[1];
        int val = connInfo.get(j)[2];
        if (dp[from] == Long.MAX_VALUE) continue;
        dp[to] = Math.min(dp[to], dp[from] + val);
    }
}

음수 사이클 체크

for (int i = 0; i < connInfo.size(); i++) {
    int from = connInfo.get(i)[0];
    int to = connInfo.get(i)[1];
    int val = connInfo.get(i)[2];
    if (dp[from] == Long.MAX_VALUE) continue;
    if (dp[to] > dp[from] + val) {
        sb.append(-1);
        return;
    }
}

정답 출력 처리

for (int i = 2; i < N + 1; i++) {
    sb.append((dp[i] == Long.MAX_VALUE) ? -1 : dp[i]).append("\n");
}

🐛 반례 / 주의할 점

문제 상황

항목	값
최대 N	500
최대 M	6000
최소 가중치	-1000

최단거리 값이 500 * 6000 * -1000 정도까지 갈 수 있음
Integer 범위 초과 위험 🚨

해결 방법 💡

최단거리 배열 dp[]를 long 타입으로 선언하여 해결

✍️ 회고 / 느낀점

접근	결과	비고
다익스트라	실패	음수 가중치/사이클 처리 불가
다익스트라 + 유니온파인드	실패	최단거리 갱신 보장 X
벨만포드	성공	음수 간선/사이클 처리 최적화

느낀 점

음수 간선, 사이클 문제 → 벨만포드 필수 고려
자료형(int vs long) 범위 체크는 습관화
문제 조건/범위 꼼꼼히 확인하기
사이클 노드 추적은 DFS/BFS 활용 가능

전체 코드

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

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N, M;
    private static List<int[]> connInfo = new ArrayList<>();
    private static long[] dp;

    public static void main(String[] args) throws IOException {
        inputSetting();
        solution();
        System.out.println(sb);
    }

    private static void solution() {
        // DP를 이용해서 최솟값을 유지하면서 진행
        // N-1번 진행, 시작점부터 최대 가능한 끝점까지 도달하기 위해 필요한 횟수
        for (int i = 0; i < N + 1; i++) {
            dp[i] = Long.MAX_VALUE;
        }
        dp[1] = 0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < connInfo.size(); j++) {
                int from = connInfo.get(j)[0];
                int to = connInfo.get(j)[1];
                int val = connInfo.get(j)[2];
                if (dp[from] == Long.MAX_VALUE) continue;
                dp[to] = Math.min(dp[to], dp[from] + val);
            }
        }

        //한번 더 실행했을때에 값이 바뀐다면 순환이 존재하는 것
        for (int i = 0; i < connInfo.size(); i++) {
            int from = connInfo.get(i)[0];
            int to = connInfo.get(i)[1];
            int val = connInfo.get(i)[2];
            if (dp[from] == Long.MAX_VALUE) continue;
            if (dp[to] > dp[from] + val) {
                sb.append(-1);
                return;
            }
        }

        for (int i = 2; i < N + 1; i++) {
            sb.append((dp[i] == Long.MAX_VALUE) ? -1 : dp[i]).append("\n");
        }
        // 추가적으로 사이클이 발생했던 노드에서 DFS, BFS를 사용하면 영향받는 노드를 모두 구할 수 있음
    }


    private static void inputSetting() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dp = new long[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            connInfo.add(new int[]{from, to, val});
        }
    }
}