백준 11780번 플로이드 2 (JAVA)

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

11780번: 플로이드 2

 

이름에서도 느껴지듯이, 플로이드 워셜 알고리즘을 사용하는 문제였다.

단순한 사용에 플러스 알파로 백트래킹을 통한 경로저장이 필요한 문제였다.

public class Main {
	static Function<String, Integer> stoi = Integer::parseInt;
	static int N, M;
	static int[][] map;
	static int[][] prev;
	static final int INF = (int) 1e9;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = stoi.apply(br.readLine());
		M = stoi.apply(br.readLine());
		map = new int[N + 1][N + 1];
		prev = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			Arrays.fill(map[i], INF);
			Arrays.fill(prev[i], -1);
		}
		StringTokenizer st;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = stoi.apply(st.nextToken());
			int e = stoi.apply(st.nextToken());
			int c = stoi.apply(st.nextToken());
			if (map[s][e] > c) {
				map[s][e] = c;
				prev[s][e] = s;
			}
		}
		floyd();
		print();
		System.out.println(sb);
	}

	private static void print() {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				sb.append(map[i][j] == INF ? "0 " : map[i][j] + " ");
			}
			sb.append("\n");
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (map[i][j] == INF) {
					sb.append("0 ");
				} else {
					Deque<Integer> route = new ArrayDeque<>();
					int now = j;
					route.push(j);

					while (i != now) {
						now = prev[i][now];
						route.push(now);
					}
					sb.append(route.size() + " ");
					while (!route.isEmpty()) {
						sb.append(route.pollFirst() + " ");
					}
				}
				sb.append("\n");
			}
		}
	}

	private static void floyd() {
		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				if (i == k) {
					continue;
				}
				for (int j = 1; j <= N; j++) {
					if (k == j || i == j) {
						continue;
					}
					if (map[i][j] > map[i][k] + map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
						prev[i][j] = prev[k][j];
					}
				}
			}
		}

	}

}