[BOJ 11657] 타임머신 (Java)

문제

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

11657번: 타임머신

 

풀이

Bellman-Ford 알고리즘이란?

최단 경로를 구하는 알고리즘 중에 하나이다. 

PS에 자주 사용되는 최단 경로 알고리즘으로 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 있다. 

벨만 포드 알고리즘의 특징은 간선의 가중치에 음수가 있을 때에도 최단 경로를 구할 수 있다는 점이다. 

음수 가중치가 있는 그래프

 

벨만 포드 알고리즘을 구현하는 단계는 아래와 같다. 

 

1. 출발 노드 설정

2. 최단 경로 저장할 자료구조 생성하여 INF 값으로 초기화 한다.

3. 아래 과정을 V(정점 개수)-1 번 반복한다.

모든 간선을 체크하면서 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 경로를 갱신

4. 3번 과정을 한 번 더 수행했을 때, 최단 경로가 갱신된다면 음수 순환 간선이 있는 것으로 판단한다.

 

참고 자료

https://www.youtube.com/watch?v=Ppimbaxm8d8&t=309s 

 

소스코드

package bellmanford;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ11657 {

    public static class Edge{
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight){
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
    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()); // 간선 개수
        int start = 1 ;

        ArrayList<Edge> edges = new ArrayList<Edge>();
        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 w = Integer.parseInt(st.nextToken());
            edges.add(new Edge(from, to, w));
        }

        long[] dist = new long[N+1];
        int INF = Integer.MAX_VALUE;
        Arrays.fill(dist, INF);
        dist[start] = 0;

        boolean isNegativeCycle = false;
        for(int i = 0; i < N; i++){
            for(Edge edge: edges){
                int from = edge.from;
                int to = edge.to;
                int weight = edge.weight;

                if(dist[from] == INF) continue;
                if(dist[to] > dist[from] + weight){
                    dist[to] = dist[from] + weight;
                    if(i == N-1) {
                        isNegativeCycle = true;
                    }
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        if(isNegativeCycle){
            bw.write(-1 + "\n");
        } else {
            for(int i = 2; i <= N; i++){
                dist[i] = (dist[i] == INF) ? -1 : dist[i];
                bw.write(dist[i] + "\n");
            }
        }
        bw.flush();
    }
}