[알고리즘] 플로이드 와샬

---

풀이

모든 정점들에 대해 서로의 최소 거리를 구하는 플로이드 와샬을 이용하여 푸는 문제이다.
단, 단순히 서로의 정점에 대한 최소값을 구하는 것이 아니라 서로의 정점을 최소값으로 가기 위해 먼저 지나야 하는 다른 정점을 구해야 하는 변형문제이다.

최종적으로 도출되는 표를 통해 해당 정점은 다른 정점으로 최소의 비용으로 이동하기 위해 처음으로 이동해야 하는 정점 뿐 아니라 그 중간의 정점들의 과정까지 전부 알 수 있게 된다.

package baekjoon.tier.gold.택배;

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

public class Main {

    static int n;
    static int[][] cost;
    static int[][] result;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        cost = new int[n+1][n+1];
        result = new int[n+1][n+1];

        for(int i = 1; i<=n; i++){
            Arrays.fill(cost[i], Integer.MAX_VALUE);
            cost[i][i] = 0;

            for(int j = 1; j<=n; j++){
                result[i][j] = j;
            }
        }

        for(int i = 0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            cost[n1][n2] = c;
            cost[n2][n1] = c;
        }

        for(int k = 1; k<= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if(cost[i][k] != Integer.MAX_VALUE && cost[k][j] != Integer.MAX_VALUE){
                        if(cost[i][j] > cost[i][k] + cost[k][j]){
                            cost[i][j] = cost[i][k] + cost[k][j];
                            result[i][j] = result[i][k];
                        }
                    }
                }
            }
        }

        for(int i = 1; i<=n; i++){
            for(int j = 1; j<= n; j++){
                if(i == j){
                    bw.write("- ");
                }else{
                    bw.write(result[i][j] + " ");
                }
            }
            bw.write("\n");
        }

        bw.flush();
    }
}

기본적으로 플로이드 와샬을 통해 cost 배열에 각 정점들에 대해 서로의 거리 최솟값을 저장한다.
단 최솟값이 갱신될 때마다 result배열에 최소값으로 이동했을 때 중간에 지나는 정점 k가 어느 곳인지를 저장해야 한다.

회고

헷갈렸던 부분은 k 정점을 바로 저장하는 것이 아니라, i에서 k를 가기 위해 들러야 하는 첫 번째 정점 정보를 저장해야 한다는 것이었다.

예를 들어 해당 문제의 예제에서 정점 1에서 정점 6으로 가기 위한 최소 경로는 1-2-5-6 이었는데,
1번에서 6번으로 가는 비용의 최솟값이 갱신되는 시점에 거쳐가는 정점 k는 5이다.
그러나 1과 5는 직접적으로 연결되어 있지 않아 5는 1에서 6으로 가기 위해 처음으로 출발하는 정점이 될 수 없다.

1에서 5로 가는 최소비용과 처음으로 거쳐야 하는 정점에 대한 정보는 이전 순회때 이미 저장되어 있으므로 1에서 6으로 가는 첫 번째 정점을 1에서 5로 가는 첫 번째 정점으로 초기화해주면 된다.

만약, 1-2-5-6이 아닌 1-5-6과 같은 상황이었어도 이미 초기에 result배열에 각 목표 정점을 첫 번째 지나야 하는 정점으로 초기화 해 두었으니 상관없다.

1과 5로 가기 위한 최소값이 다른 정점을 지나지 않고 둘 간의 간선으로 이동하는 경우 1에서 5로 가기 위해 첫 번째 지나야 하는 정점 정보가 5로 저장되어 있기 때문이다.