[BOJ] 11657 타임머신

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘

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

11657번: 타임머신

---

📍 고려해야할 점

• C < 0 인 경우 타임머신으로 시간을 되돌아가는 경우이다. ➔ 음의 가중치 존재 
• 1번 도시에서 출발한다. 
• 음의 사이클이 있거나 경로가 아예 없다면 -1 출력
• 오버플로우 범위 조심 

 

🕹️ 풀이과정

1️⃣ 간선과 정점, 비용의 정보를 저장한다.

2️⃣ 벨만 포드 알고리즘을 사용해서 최단 시간을 구한다. 

3️⃣ 음의 사이클이 존재한다면 -1을 출력한다. 

 

 

 

👩‍💻 전체 코드 

public class BOJ_11657_타임머신 {

    static int N, M;
    static ArrayList<Info>[] bus;
    static long[] dist;
    static int INF = 1000000000;

    static class Info{
        int to, time;

        public Info(int to, int time) {
            this.to = to;
            this.time = time;
        }
    }

    static boolean bellmanFord(){
        dist[1] = 0;

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < bus.length; j++) {
                for (Info next : bus[j]) {

                    if (dist[j] == INF) break;
                    if (dist[next.to] > next.time + dist[j]) {
                        dist[next.to] = next.time + dist[j];
                    }
                }
            }
        }

        for (int j = 1; j < bus.length; j++) {
            for (Info next : bus[j]) {
                if(dist[j] == INF)  break;
                if (dist[next.to] > next.time + dist[j]) {
                    return true; // 음의 사이클 존재
                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        bus = new ArrayList[N + 1];
        dist = new long[N + 1];
        Arrays.fill(dist, INF);

        for(int i=1; i<=N; i++){
            bus[i] = new ArrayList<>();
        }

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

            bus[a].add(new Info(b, c));
        }

        StringBuilder sb = new StringBuilder();
        if (bellmanFord()) { // 음의 사이클이 있으면 -1 출력하고 끝
            sb.append("-1");
        } else {
            for (int i = 2; i <= N; i++) {
				// 음의 사이클이 없으면 최단 경로 출력하고, 경로가 아예 없으면 -1 출력
                if (dist[i] == INF) {
                    sb.append(-1 + "\n");
                }else{
                    sb.append(dist[i] + "\n");
                }
            }
        }
        System.out.println(sb);
    }
}