[Java] 백준 11657번 : 타임머신

1. 문제

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

11657번: 타임머신

 

 

2. 풀이 과정

최단 경로를 구하는 데, 경로의 cost가 음수가 될 수 있기 때문에 Bellman-Ford 알고리즘을 사용했다.

평소에 잘 풀어보지 않았던 유형이라서 시간이 걸렸다..

 

벨만-포드 알고리즘은 다익스트라와 유사한데,

다익스트라는 현재 연결된 노드에서 갈 수 있는 경로를 살펴보며 값을 업데이트하는 반면

벨만-포드 알고리즘은 모든 경로를 보면서 최단 경로를 업데이트해가는데

N-1(가능한 최대 길이)만큼 경로 업데이트를 한 후, 한 번 더 검사했을 때 더 짧은 경로가 있다면 음수로 된 사이클이 있는 것이다.

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

public class Main {
    static class Edge {
        int start, end, cost;

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

    static int N, M;
    static final long INF = Long.MAX_VALUE;
    static Edge[] arr;
    static long[] distance;

    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());
        arr = new Edge[M];
        distance = new long[N + 1];
        Arrays.fill(distance, INF);

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

            arr[i] = new Edge(A, B, C);
        }

        BellmanFord(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= N; i++) {
            if (distance[i] == INF) {
                sb.append("-1\n");
            } else {
                sb.append(distance[i]).append("\n");
            }
        }
        System.out.println(sb);
    }

    public static void BellmanFord(int start) {
        distance[start] = 0;

        for (int i = 0; i < N; i++) {
            for (Edge edge : arr) {
                if (distance[edge.start] != INF && distance[edge.end] > distance[edge.start] + edge.cost) {
                    distance[edge.end] = distance[edge.start] + edge.cost;
                }
            }
        }

        for(Edge edge : arr) {
            if (distance[edge.start] != INF && distance[edge.end] > distance[edge.start] + edge.cost) {
                System.out.println("-1");
                System.exit(0);
            }
        }

    }

}

 

 

결과