[BOJ]第11780号フロイド2(Java)

質問する (Gold 2)

11780号:フロイド2

に答える

「Floyd-Warshallアルゴリズム」を使用します.すべてのパスの最低コストを探す必要があるからです.
最小コストに加えて、パスの内容も保存する必要があります.そのため、2 D配列変数も宣言します.
map[i][j]:i->jパスを格納する最低コスト
path[i][j]:iからjまで通る都市
経路kを通る道(map[i][j])が直接来た道(map[i][k]+map[k][j])よりも速い場合. 
最低コストを保存し、jに到着する前に来路を保存します!
パスi->jはi->k->jとなっているため、path[i][j]はjに到達する前に到達したpathとして保存される[k][j]

パス出力ロジック

i->j パス. n.ハル もしそうなら、
jの前に聞こえた場所に乗り続けた 会うまで. スタッキング に参加 繰り返し ろんり
\=> 最後に 到着点から 開始点 他郷 ぎゃくてん 他郷 柿

コード#コード#

package shortestPath;

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

public class Main_11780_플로이드 {
    static final int INF = 10000001;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] map = new int[n+1][n+1];    // 최단경로 저장
        int[][] path = new int[n+1][n+1];   // 도착점으로 가기 직전에 들린 점 저장


        for(int i = 0 ; i < n+1 ; i++){
            for(int j = 0 ; j < n + 1 ; j++){
                if(i == j){
                    map[i][j] = 0;
                    path[i][j] = INF;
                }else{
                    map[i][j] = INF;
                    path[i][j] = INF;
                }
            }
        }

        for(int i = 0 ; i < m ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            map[start][end] = Math.min(map[start][end], cost);  // 이미 저장되어 있을 지 모르니까, 최솟값 저장
            path[start][end] = start;
        }

        for(int k =1 ; k < n+1 ; k ++){
            for(int i = 1; i < n+1 ; i++){
                for(int j = 1 ; j < n+1 ; j++){
                    if(i!=j && map[i][j] > map[i][k] + map[k][j]){  // 바로 오는 길(map[i][j])보다 경로 k를 거쳐서 오는 길(map[i][k] + map[k][j])이 더 빠를 경우
                        map[i][j] = map[i][k] + map[k][j];  // 최소 비용 저장
                        path[i][j] = path[k][j];    // 도착점 j로 가기 전에, 들른 곳(path[k][j]) 저장
                    }
                }
            }
        }

        for(int i = 1 ; i < n +1 ; i++){
            for(int j = 1; j < n+1 ; j++){
                sb.append(map[i][j]==INF ? 0+" " : map[i][j]+" ");  // 최소 비용 출력
            }
            sb.append("\n");
        }

        Stack<Integer> stack = new Stack<>();

        for(int i = 1 ; i < n+1 ; i++){
            for(int j = 1 ; j < n+1 ; j++){
                if(path[i][j] == INF) sb.append("0\n"); // 갈 수 없는 경우
                else{
                    int end = j;
                    stack.push(end);
                    /*
                        i->j 경로라고 할 경우,
                        j전에 들렸던 곳을 계속해서 타고 가서
                        i를 만날때까지 스택에 넣으며 반복하는 로직
                        => 마지막 도착점부터 시작점까지 타고 거꾸로 타고 감
                     */
                    while( i != path[i][end] ){
                        end = path[i][end];
                        stack.push(end);
                    }
                    stack.push(i);  // 마지막인 시작점도 출력해야 하므로!
                    sb.append(stack.size());
                    while(!stack.isEmpty()){    // 시작점부터 마지막점까지 출력(stack > FILO)
                        sb.append(" "+stack.pop());
                    }
                    sb.append("\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}