[백준(Baekjoon)][자바(java)] 11780 : 플로이드 2 / 동적 계획법과 최단거리 역추적

 

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

11780번: 플로이드 2

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), m = Integer.parseInt(br.readLine()), N = n + 1;
		int u, v, w, i, j, k;
		int[][] edge = new int[N][N], 
				dp = new int[N][N]; // i에서 j까지 갈 때 거치는 도시 (이전 도시)
		StringTokenizer st;
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			edge[u][v] = edge[u][v] > 0 ? Math.min(edge[u][v], w) : w;
			dp[u][v] = u;
		}
		br.close();

		int[][] cost = new int[N][N]; // i에서 j까지 가는 데에 드는 최소 비용	
		for (i = 1; i <= n; ++i)
			for (j = 1; j <= n; ++j)
				cost[i][j] = edge[i][j];
		for (k = 1; k <= n; ++k) {			// 중간 정점 집합
			for (i = 1; i <= n; ++i) {		// 시작 정점
				for (j = 1; j <= n; ++j) {	// 마지막 정점
					if (i == j || cost[i][k] == 0 || cost[k][j] == 0) continue;
					if (cost[i][j] == 0 || (cost[i][j] > cost[i][k] + cost[k][j])) {
						cost[i][j] = cost[i][k] + cost[k][j];
						dp[i][j] = dp[k][j];
					}
				}
			}
		}
		
		StringBuilder answer = new StringBuilder(), path;
		for (i = 1; i <= n; ++i) {
			for (j = 1; j <= n; ++j)
				answer.append(cost[i][j] + " ");
			answer.append("\n");
		}
		int jj, cnt;
		for (i = 1; i <= n; ++i) {
			for (j = 1; j <= n; ++j) {
				if (i == j || cost[i][j] == 0) {
					answer.append("0\n");
					continue;
				}
				path = new StringBuilder();
				jj = j; cnt = 1;
				path.append(jj + "\n");
				while (cost[i][jj] > 0) {
					cnt++;
					path.insert(0, (jj = dp[i][jj]) + " ");
				}
				path.insert(0, cnt + " ");
				answer.append(path.toString());
			}
		}
		System.out.println(answer.toString());
	}
}