[Java] 벨만-포드 (타임머신)

한창 타임머신에 관해 연구하고 있던 찰나에 나의 흥미를 돋우는 제목의 문제를 발견했다.

 

해당 문제를 풀면서 graph를 class Node를 이용해 구성하였다. 특이점은 Node에 출발점, 도착점, 가중치를 모두 선언하지 않고 도착점, 가중치만 구성하여서 해당 Node가 있는 index가 출발점 역할을 하도록 했다.

처음에는 파이썬에서의 버릇 때문에 위와 같이 구성했는데 생각해 보면 만약 한 정점에서만 출발하는 간선이 많을 경우 비효율 적으로 예상됨에 따라 Node에 출발점, 도착점, 가중치를 모두 선언하고 하나의 ArrayList에 선언하는 것도 좋을 것 같다.

또 벨만-포드 알고리즘에서 왜 V-1번만 반복해야 하는지 의문을 해소하지 못했다.

 

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

11657번: 타임머신

 

 

 

해당 문제는 최단거리를 구하는 문제이므로 다익스트라 알고리즘을 사용해야 하지만 음의간선이 존재하기 때문에 벨만-포드 알고리즘을 사용해서 풀어야 한다.

 

문제를 푸는 순서는 다음과 같다.

1. 다음 정점과 가중치의 정보를 담은 graph 구성

2. 출발 노드를 설정.

3. 최단 거리 테이블 distance 배열을 초기화.

4. 다음의 과정을 V-1번 반복.

 4-1. 전체 간선을 하나씩 확인.

 4-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 distance 갱신.

5. V-1번 반복 후 한번 더 check 함수를 이용해 최단 거리 테이블을 갱신했을 때 만약 갱신되는 테이블이 있다면 값이 무한히 작아질 수 있는 루프에 빠진 것이므로 false를 return

 

중요!

문제의 주어진 변수들의 범위를 봤을 때 distance의 값이 int형의 최솟값을 벗어날 수 있기 때문에 distance를 long으로 선언해야 한다.

 

 

 

 

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

import static java.lang.System.exit;


class Node{
    int v; //v로 이동
    int w; //가중치

    Node(int v, int w){
        this.v = v;
        this.w = w;
    }
}

public class Main {

    static Integer INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        int V = Integer.parseInt(st.nextToken()); //정점 (도시 수)
        int E = Integer.parseInt(st.nextToken()); //간선의 개수 (버스 수)
        int u,v,w; //u에서 v로 이동할 때 가중치 w

        ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
        //python의 [[new Node(), new Node()],[],[]...]
        for (int i=0; i<V+1; i++){
            graph.add(new ArrayList<>());
        }



        long[] distnace = new long[V+1];
        //1번 도시에서 출발해서 각 정점 까지의 거리 언더플로우 방지를 위해 long 자료형

        Arrays.fill(distnace, INF);

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            graph.get(u).add(new Node(v,w));
        }

        ford(1, V, graph, distnace);

        if(check(1, V, graph, distnace) == false) {System.out.println(-1); exit(0);};

        for(int i=1; i<distnace.length; i++){ //정점은 1부터 시작함 (distance[0]은 더미값)
            if(i==1) continue;
            if(distnace[i] == INF) {System.out.println(-1); continue;}
            System.out.println(distnace[i]);
        }

    }

    public static void ford(int start, int V, ArrayList<ArrayList<Node>> graph, long[] distnace){

        distnace[start] = 0;

        for(int k=0; k<V-1; k++) { //벨만-포드 알고리즘 V-1 만큼 반복

            for (int i = 1; i < V + 1; i++) {

                for (int j = 0; j < graph.get(i).size(); j++) {

                    Node ac_node = graph.get(i).get(j); //access Node (접근 노드)

                    int cur_node = i; //현재 정점
                    int next_node = ac_node.v; //다음 정점

                    if (distnace[cur_node] != INF && distnace[next_node] > distnace[cur_node] + ac_node.w) {
                        //출발 정점에서 현재 정점으로 까지 거리가 무한대 즉 경로가 없다면 CONTINUE
                        distnace[next_node] = distnace[cur_node] + ac_node.w;
                    }
                }
            }
        }

    }

    public static boolean check(int start, int V, ArrayList<ArrayList<Node>> graph, long[] distnace){

        for(int i=1; i<V+1; i++){

            for(int j=0; j< graph.get(i).size(); j++){

                Node ac_node = graph.get(i).get(j); //access Node (접근 노드)

                int cur_node = i; //현재 정점
                int next_node = ac_node.v; //다음 정점

                if(distnace[cur_node] != INF && distnace[next_node] > distnace[cur_node]+ac_node.w){
                    return false; //만약 갱신되는 값이 있다면 무한루프에 빠진것이므로 false return
                }

            }
        }
        return true;
    }

}