[PS] 백준 11404번 플로이드

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

문제 설명

정점 n(n <= 100)개, 간선 m(m <= 100,000)개인 가중 그래프에서 모든 정점 간의 최단 거리를 출력하는 문제이다. 단, 가중치는 100,000이하의 자연수이고 도달하지 못하는 경우는 최단 거리 대신 0을 출력한다.

문제 풀이

문제 제목에 나와있듯이 플로이드-워셜 알고리즘을 이용하면 된다. 플로이드-워셜 알고리즘은 음수 사이클이 없는 가중 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘이다. 음수 사이클만 없으면 되므로 음수 가중치가 존재해도 올바른 답을 구할 수 있다는 점도 기억해야 할 포인트이다. 왜냐하면 한 정점에서 다른 모든 정점으로의 최단 거리를 구하는 다익스트라 알고리즘은 음수 가중치가 허용되지 않기 때문이다.

여기서 음수 사이클이란, 사이클을 구성하는 간선들의 가중치 합이 음수인 사이클이다. 음수 사이클이 허용되지 않는 이유는 간단하다. 그 경로의 길이가 무한으로 낮아질 수 있기 때문에 논외로 치는 것.

플로이드-워셜 알고리즘은 Dynamic Programming 유형에 속한다. 1~k 번째까지를 경유지로 사용가능한 경우의 최단거리를 구한 상태에서, 1~k+1 번째까지를 경유지로 사용가능한 경우의 최단거리를 구해가기 때문이다. (경유지로 반드시 사용한다는 것이 아니라 경유지로 고려하는 경우와 하지 않는 경우 중에 최적을 취한다는 말이다.)

앞에서 k개의 정점(1, 2, ..., k번째)을 경유해서 i -> j 로 가는 최단 거리 := shortest(i, j, k) 라고 정의하면, 아래와 같이 점화식이 정의된다.

shortest(i, j, k) := min(shortest(i, j, k - 1), shortest(i, k, k - 1) + shortest(k, j, k - 1))
shortest(i, j, 0) := adj[i][j]

위 점화식을 순서에 맞게 반복문으로 구현하면 된다. 기본적으로 플로이드-워셜 알고리즘은 최단 경로의 길이만 구하고 그 경로를 구하지는 않는다. 그러나 조금의 수정만 가하면 경로를 구할 수 있다.
음수 사이클도 감지해 낼 수 있다. i -> i 의 최단거리를 저장하는 곳의 값이 음수가 되는 경우, 음수 사이클이 존재한다는 뜻이된다.
보통 adjacency matrix 자체를 최단경로의 길이 배열로 바꾸는 식으로 구현한다. 다만 초기 값을 갈 수 없는 경우 양의 infinite로 설정, i == i 인 경우 0으로 설정한다.
만약 i == i 인 곳의 값을 양의 infinite 로 설정하면 각 정점에서 자기 자신으로 돌아오는 거리가 0이 아닌 경로의 길이도 결과 배열에 담기게 된다.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int n, m;
	static int[][] adj;
	static final int INF = 100_000_001;

	public static void main(String[] args) throws Exception {
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());

		adj = new int[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			Arrays.fill(adj[i], INF);
			adj[i][i] = 0;
		}

		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 cost = Integer.parseInt(st.nextToken());

			adj[from][to] = Math.min(adj[from][to], cost);
		}

		floydWarshall();

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				bw.append((adj[i][j] >= INF ? 0 : adj[i][j]) + " ");
			}

			bw.append('\n');
		}

		bw.flush();
	}

	static void floydWarshall() {
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
				}
			}
		}
	}
}