[BOJ][Java] 11657번 타임머신

문제 설명

문제 링크 : https://www.acmicpc.net/problem/11657

 

이 문제는 1번 도시에서 출발해서 각 도시까지의 최단 거리를 출력하는 문제이다. 

여기까지만 보면 다익스트라 알고리즘을 이용하면 될 것처럼 보이지만

다익스트라 알고리즘을 사용하기 위한 조건중 하나는 무조건 에지가 양수여야 한다는 것이다.

하지만 이 문제를 조건을 보면 에지의 값이 음수도 가능하다. 따라서 다익스트라가 아닌

벨만 포드 알고리즘을 사용해서 풀어야 한다.

 

벨만 포드 알고리즘은 시작 정점부터 각각의 정점까지의 최단거리도 구할 수 있지만 음수 사이클이 존재하는지

여부도 알 수 있다.

 

예제 1번을 보면 위와 같이 음수 사이클이 생성되는 것을 알 수 있다.

 

벨만 포드 알고리즘을 수행하기 위해서 우선 거리배열을 선언하는데 이때 출발 정점인 1번 정점은 0으로

나머지 정점들은 무한대(문제에 따라서 Long.MAX_VALUE 혹은 Integer.MAX_VALUE)로 선언해 주면 된다.

거리배열을 업데이트할 때는 위와 같은 조건이 성립할 때만 거리배열을 업데이트해준다. 또한 이때 아직 한 번도 방문하지 않은

(거리배열이 무한대) 정점이 시작정점이 되는 경우에는 값을 업데이트하면 안 된다.

벨만 포드 알고리즘은 정점의 개수가 N개일 때

주어진 에지를 총 N-1번 수행했을 때 출발 정점에서부터 각 정점까지의 최소 거리를 구할 수 있다.

 

주어진 에지를 모두 한 번씩 사용했다고 했을 때의 거리 배열의 값은 위와 같다.

 

에지를 2번 사용하면 위와 같은 거리배열을 얻을 수 있다.

만약 음수사이클이 없다면 여기서 한 번 더 실행해도 거리배열은 바뀌지 않는다.

만약 음수 사이클이 있다면 한번 더 실행했을 때 값이 바뀌게 되고 그것을 통해 음수사이클이

존재하는지 여부를 판별할 수 있다.

 

package boj;

import java.util.*;
import java.io.*;

public class BOJ11657 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Node[] edges = new Node[m];
        long[] dist = new long[n+1];

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            edges[i] = new Node(u,v,w);
        }

        for(int i = 1; i < dist.length; i++){
            dist[i] = Long.MAX_VALUE;
        }

        dist[1] = 0;

        for(int i = 0; i < n-1; i++){
            for(int j = 0; j < m; j++){
                if(dist[edges[j].start] != Long.MAX_VALUE && dist[edges[j].end] > dist[edges[j].start] + edges[j].cost){
                    dist[edges[j].end] = dist[edges[j].start] + edges[j].cost;
                }
            }
        }

        boolean flag = false;

        for(int i = 0; i < m; i++){
            if(dist[edges[i].start] != Long.MAX_VALUE && dist[edges[i].end] > dist[edges[i].start] + edges[i].cost){
                flag = true;
                break;
            }
        }

        StringBuilder sb = new StringBuilder();

        if(flag) System.out.println(-1);
        else{
            for(int i = 2; i < dist.length; i++){
                if(dist[i] != Long.MAX_VALUE) sb.append(dist[i]).append("\n");
                else sb.append(-1).append("\n");
            }

            System.out.println(sb);
        }




    }
    static class Node {
        int start;
        int end;
        int cost;

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