[JAVA] 백준 11780번 - 플로이드 2

7달 전에 C++로 풀이를 했었는데 재채점 되어 다시 풀어본 문제입니다. 

100%에서 틀리시는 분들은 아래의 반례로 해답을 찾으실 수 있을 것 같습니다.

4
4
1 2 1
1 3 1
3 2 1
2 1 1

(갈 수 없는 경로에는 0이 출력돼야 하는 반례)

 

📖 문제

 

📋 코드

import java.util.*;

public class Main {

	public static int n;
	public static int m;
	public static int cost[][] = new int[101][101];
	public static int route[][] = new int[101][101];

	public static void path(int start, int n) {
		for (int end = 1; end <= n; end++) {
			if (start == end)
				System.out.println(0);
			else {
				Stack<Integer> st = new Stack<>();
				int idx = route[start][end];
				while (idx != 0) {
					st.push(idx);
					idx = route[start][idx];
				}
				
				if(st.empty()) { // start에서 end로 갈 수 없는 경우
					System.out.println(0);
				}
				else { // 경로 출력
					System.out.print(st.size() + 1 + " ");
					while (!st.empty()) {
						System.out.print(st.peek() + " ");
						st.pop();
					}
					System.out.println(end);
				}
			}
		}
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i != j)
					cost[i][j] = 1000001;
			}
		}

		for (int i = 1; i <= m; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			cost[x][y] = Math.min(cost[x][y], sc.nextInt());
			route[x][y] = x;

		}

		// 플로이드 와샬
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (cost[i][j] > cost[i][k] + cost[k][j]) {
						cost[i][j] = cost[i][k] + cost[k][j];
						route[i][j] = route[k][j];
					}
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(cost[i][j] <= 100000) {
					System.out.print(cost[i][j] + " ");
				}else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}

		for (int i = 1; i <= n; i++) {
			path(i, n);
		}

	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

플로이드 와샬로 최단경로를 구하고 경로를 구하면서 최단 경로가 갱신될 때마다 route배열에 기록하였습니다.

그리고 path함수를 작성하여 경로들을 추적해 역순으로 스택에 담고 다시 top부터 pop 하면서 경로들을 출력하였습니다.

 

 

🔗 링크

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

11780번: 플로이드 2