백준/11404번/Java - 플로이드 (플로이드-와샬)

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

11404번: 플로이드

---

최소비용 배열 전체를 구하는 문제로, 플로이드-와샬 알고리즘을 적용하여 푼다.

 

전체 경로가 최단 경로이기 위해서는 전체 경로를 이루는 부분 경로들 역시 최단 경로를 이뤄야 한다는 점을 이용한다.

 

다익스트라는 인접리스트를, 벨만-포드는 간선배열을 활용했지만 플로이드-워셜은 인접행렬을 통해 문제를 푼다.

 

인접 행렬에 i노드에서 j노드까지의 가중치를 표시하고, 간선이 연결되지 않은 경우에는 무한대를 표시한다.

 

이후 플로이드 와샬 알고리즘을 실행한다.

 

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

public class Main {

    //최소비용 배열
    static long[][] D;

    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        D = new long[N+1][N+1];
        //N의 크기가 최대 100이므로 시간 복잡도의 최대는 1000000. N이 너무 크면 플로이드 와샬을 적용할 수 없다.

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i == j) D[i][j] = 0;
                else D[i][j] = Integer.MAX_VALUE;
            }
        }

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

            D[start][end] = Math.min(D[start][end], cost);
        }

        floyd();

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                long num = (D[i][j] == Integer.MAX_VALUE) ? 0 : D[i][j];
                bw.write(num+ " ");
            }
            bw.write("\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static void floyd() {
        /*
        전체의 최단경로는 부분 경로들 역시 최단 경로여야 한다.
        S에서 출발해 바로 E로 오는 거리와 S에서 출발해 K를 거쳐 E로 오는 거리 중 더 짧은 것이 최단경로가 된다.
         */
        //경유지 K
        //출발노드
        //도착노드 순으로 3중 for문
        for(int k=1; k<=N; k++) {
            for(int s=1; s<=N; s++) {
                for(int e=1; e<=N; e++) {
                    D[s][e] = Math.min(D[s][e], D[k][e]+D[s][k]); //
                }
            }
        }
    }
}