11657번 타임머신 ( JAVA )

벨만 포드를 오랜만에 봤더니 기억이 잘 나질않아서 어려웠다.

 

벨만 포드 알고리즘이란 ?

한 지점에서 다른 모든 지점까지 최단 경로를 찾는 알고리즘은 다익스트라와 벨만 포드가 있다.

여기서 두 알고리즘의 차이는 무엇이냐 ?!!

바로 속도 차이다. 다익스트라가 벨만 포드보다 빠르다. 이유는 다익스트라의 동작 방식은 방문하지 않은 정점 중에서 가장 비용이 적은 노드를 선택한다. 해당 정점을 거쳐서 다른 정점을 가는 경우를 고려하여 최비용을 갱신한다. 이 부분을 반복한다.

이런식으로 하면 편하게 생각해서 정점 갯수 만큼 동작하면 갱신된다 ( (정점,도착비용)을 우선순위 큐에 넣고 최단인 경우 정점을 방문하고 그 외는 다른 동작을 하지않음 )

 

그치만 다익스트라는 음수가 포함되어있으면 제대로 동작되지 않는다. 그렇기때문에 다익스트라를 사용할 수 없는 경우에 벨만 포드 알고리즘이 사용된다.

벨만 포드는 간단하다. 

(정점의 갯수 - 1)번 동안 모든 간선을 확인하면서 최소값으로 갱신하면 최단거리가 나온다.

(정점의 갯수 - 1)번은 가장 긴 최단거리는 1 에서 n을 간다고 할때 1 - 2 -3 -...-n 의 결과이기때문에 n까지 V - 1번 갱신하면된다. ( 물론 그 이전에 구해질 수도 있다. )

여기서 중요한 점은 최단거리를 구하고나서 한번 더! 모든 간선을 확인하면서 최소값을 갱신했을때 갱신이 된다면 음의 사이클이 존재하는 것이다. 그렇기 때문에 최단거리를 구할 수없다 ( 값이 계속 작아져요 )

 

자 이제 이론은 다 배웠다.

 

접근방법

1. 벨만 포드를 사용한다.

입 / 출력

입력	3 2 2 3 -1 3 2 -2
출력	-1 -1

 

코드

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

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    static int readInt() throws IOException {
        if (Objects.isNull(token) || !token.hasMoreTokens()) {
            token = new StringTokenizer(reader.readLine());
        }
        return Integer.parseInt(token.nextToken());
    }

    static class Node {
        int v, cost;

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

    public static void main(String[] arg) throws IOException {
        int vertexSize = readInt();
        int edgeSize = readInt();
        List<List<Node>> bus = new ArrayList<>();
        for (int i = 0; i <= vertexSize; i++) {
            bus.add(new ArrayList<>());
        }
        for (int i = 0; i < edgeSize; i++) {
            int u = readInt();
            int v = readInt();
            int cost = readInt();

            bus.get(u).add(new Node(v, cost));
        }

        long[] distances = new long[vertexSize + 1];

        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[1] = 0;

        for (int i = 0; i < vertexSize - 1; i++) {
            for (int j = 1; j <= vertexSize; j++) {
                for (Node next : bus.get(j)) {
                    if (distances[j] != Integer.MAX_VALUE && distances[j] + next.cost < distances[next.v]) {
                        distances[next.v] = distances[j] + next.cost;
                    }
                }
            }
        }

        long compareDistance[] = distances.clone();
        for (int i = 1; i <= vertexSize; i++) {
            for (Node next : bus.get(i)) {
                if (distances[i] != Integer.MAX_VALUE && distances[i] + next.cost < distances[next.v]) {
                    distances[next.v] = distances[i] + next.cost;
                }
            }
        }
        for (int i = 1; i < vertexSize; i++) {
            if (compareDistance[i] != distances[i]) {
                System.out.println("-1");
                return;
            }
        }
        for (int i = 2; i <= vertexSize; i++) {
            System.out.println(distances[i] == Integer.MAX_VALUE ? -1 : distances[i]);
        }

    }
}

1. 벨만 포드 알고리즘 탐색을 할때 최단거리를 갱신할때 현재 위치 비용이 최댓값 ( INF ) 일 경우에 코드가 동작하지 않게 설정해야된다. 음수의 간선을 가지고 있는 경우에 갱신되는 경우가 생기기때문이다.

2. 언더플로우가 발생할 수 있다. 자료형을 long으로 설정해야된다. 이유는 정점이 500개 이고 노선의 갯수가 6000개 일때 모든 간선이 -10000을 가지고 있다면 간선이 계속 줄어든다.  500*6000 번 감소된다. (1번 할때마다 -10000씩 갱신된다)