boj 11780: 플로이드2

플로이드 알고리즘: 모든 쌍의 최단 경로를 구하는 알고리즘

c.f. 벨만 포드/다익스트라 알고리즘: 시작점이 1개일 때

 

이 문제는 플로이드 알고리즘을 써서 풀 수 있다.

그런데, 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 K를 출력해야 하기때문에

그동안 지나왔던 경로도 저장해야 한다.

 

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

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], 1000000);
			mat[i][i] = 0;
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int cost = in.nextInt();
			mat[start][end] = Math.min(mat[start][end], cost);
		}

		int route[][] = new int[n + 1][n + 1];
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (mat[i][j] > mat[i][k] + mat[k][j]) {
						route[i][j] = k; // i~j를 갈 때 k를 거친다
						mat[i][j] = mat[i][k] + mat[k][j];
					}
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.print(mat[i][j] + " ");
			}
			System.out.println();
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					System.out.println("0");
				} else {
					LinkedList<Integer> list = new LinkedList<Integer>();
					routeList(i, j, route, list);
					System.out.print(list.size() + " ");
					for (int k = 0; k < list.size(); k++) {
						System.out.print(list.get(k) + " ");
					}
					System.out.println();
				}
			}
		}
	}

	public static void routeList(int start, int end, int route[][], LinkedList<Integer> list) {
		if (route[start][end] == 0) { // i~j를 갈 때 거치는 점이 없을
			list.add(start);
			if (start != end) {
				list.add(end);
			}
		} else {
			int middle = route[start][end]; // i~j를 갈 때 경유
			routeList(start, middle, route, list);
			list.removeLast(); // 중복 제거
			routeList(middle, end, route, list);
		}
	}
}

그동안 지나왔던 경로를 저장할 때에는 route[i][j]에 i와 j를 지날 때 경유한 점을 저장하도록 한다.

즉, route[i][j]에는 i->j 간선이 원래 어디를 가르켰는지 저장한다.

경유했던 점들의 리스트를 가져올 때에는 routeList에서 list에 하나씩 넣는데

routeList(start, middle, route, list)와 routeList(middle, end, route, list)에서 middle 부분이 list에 두번 중복되어 들어가므로 한 번 제거해줘야한다.