[백준] 11657번: 타임머신 - java

 

 

음수가중치가 있는 문제이므로 다익스트라로는 최단 경로를 갱신할 수 없다.

=> 다익스트라는 이미 방문한 노드에 대해서는 더 이상 경로탐색을 하지 않기에 (더 탐색하면 양의 가중치를 더 얻게 되므로 당연히 탐색할 필요X) 최단 경로를 판별할 수 없다.

 

따라서 벨만포드를 사용해서 모든 edge에 대해서 edge relaxation 을 (V-1) 번 수행해준다.

 

그런데 왜 V-1 만큼일까? 

V-1 만큼 모든 간선을 탐색하는 것이 확 와닿지가 않았다.

그림으로 이해해보자.

출발점이 A라고 생각해보자.

1번째 방문시, 다음과 같이 갱신이 된다.

사실 A->D 간선이 먼저 갱신된다면 1번째 방문에서 D->C 도 갱신되겠지만,

최악의 경우를 고려했을 때는 아래와 같다. 간선의 순서와 상관없이 A에서 출발하는 간선의 끝에 있는 정점에는 도달할 수 있다.

 

2번째 방문이다.

이제 B,C,D 까지의 dist 값이 무한대가 아니므로, D->B , D->C 로도 갱신이 가능해졌다.

 

마지막으로 3번째 방문이다.

이미 모든 정점의 갱신이 이루어진 상태이다.

 

즉, 최악의 경우 V-1 만큼의 정점개수만큼 모든 간선에 대해 갱신을 시도해야만 모든 정점에 대해 최단경로가 갱신되는 것이다.

 

ex) 또다른 예시를 보자.

주어진 간선이 [ 1->2, 3->2, 4->3, 5->4 ] 순서로 저장되어 있다고 가정해보자.

이때는 V-1 인 4라운드를 모두 돌아야지만 모든 정점경로가 갱신된다.

따라서 최악의 경우에도 V-1 만큼을 돈다면 모든 정점에 대해 최단경로를 갱신할 수 있다!!!!

 

**** 주의 ****

처음에는 dist[] 를 int로 두었더니 출력초과가 났다.

왜때문에 출력초과가 발생했는지 의문이 든다면?,,, 일단 결론부터 말하자면 underflow때문이다.

문제에서 주어진 조건인 정점의 개수가 500개, 간선의 개수가 6000개, 최소 가중치가 -10000이라면 충분히 underflow가 발생할 수 있는 수치이다.

(-500 * 6000 * 10000 = -3 * 10^10, Integer.MIN_VALUE = 약 -2*10^9)

 

우선 -1을 출력하는 조건은 '정점의 개수를 V라 할 때, V - 1번 만큼 최소값을 충분히 갱신해주고 V번째에서 최소값이 갱신 되는 경우이다.

 

그리고 이런 경우가 있다고 가정해보자.

- 정점 V: 500개 (1에서 출발)

- 간선 E: 6000개 (1에서 2로 가며 가중치는 -10000, 2에서 1로가며 가중치는 -10000 ...반복 ...)

벨만-포드 알고리즘에서의 내부 반복문이 1번 회전한다면 2로 가는 비용은 -10000로 갱신, 3번 회전한다면 2로 가는 비용은 -30000으로 갱신..... 을 반복하다가,

이런 과정을 거쳐서 외부 반복문이 한 번 회전한다면 2로 가는 비용은 -60000000로 갱신된다.

 

즉, dist[edge.v] > dist[edge.u] + edge.w 조건에서 언더플로우가 발생해서, 최단경로가 갱신이 되지 않는다.

 

따라서 이 경우는 음의사이클이 발생하지만, 언더플로우로 인해 v==n일때 dist[edge.v] > dist[edge.u] + edge.w  조건을 만족하지 못하고,

이는 무한히 오래 전으로 되돌릴 수 있는 경우라고 판단되지 않아 "-1" 을 출력하지 못하게 된다.

 

=> dist[] 을 long으로 둔다면, -3 * 10^10 의 값을 담을 수 있기에 최단경로를 갱신할 수 있다.

 

 

코드

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb;
	static StringTokenizer st;
	static int n, m, a, b, c;
	static long dist[];
	static ArrayList<Edge> edges;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		edges = new ArrayList<>();

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			edges.add(new Edge(a, b, c));
		}

		dist = new long[n + 1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[1] = 0;
		boolean cycle = false;
		for (int i = 1; i <= n; i++) {
			for (Edge edge : edges) {
				if (dist[edge.u] != Integer.MAX_VALUE && dist[edge.v] > dist[edge.u] + edge.w) {
					dist[edge.v] = dist[edge.u] + edge.w;
					if (i == n) {
						cycle = true;
						break;
					}
				}
			}
		}
		if (cycle)
			System.out.println(-1);
		else {
			for (int i = 2; i <= n; i++) {
				if (dist[i] == Integer.MAX_VALUE)	
					System.out.println(-1);
				else	
					System.out.println(dist[i]);
			}
		}

	}

	static class Edge {
		int u;
		int v;
		int w;

		public Edge(int u, int v, int w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}

	}
}