[JAVA] 백준 11404 플로이드-워셜

 

 

 

 

11404번: 플로이드

문제

모든 도시에 대해서 다른 모든 도시로의 최단 거리를 구하는 문제입니다.

플로이드-워셜 알고리즘을 통해 문제를 해결하였습니다.

풀이

플로이드-워셜

플로이드-워셜 알고리즘은 모든 도시에 대해서 다른 모든 도시로의 최단 거리를 구하는 문제입니다.

이 거리는 음수 가중치가 있더라도 동작하며 시간 복잡도는 $O(N^3)$으로 매우 큰 편입니다.

따라서 입력 정점이 작다는 특징도 있습니다.

플로이드 워셜은 다음과 같은 단계를 통해 값을 구해냅니다.

1. 모든 도시에 대해서 다른 모든 도시로의 최단 거리를 구해야 하기 때문에 2차원 배열을 통해 거리를 계산합니다.
   • 2차원 배열을 선언하고 충분히 큰 수로 초기화 해줍니다. 단, 현재 도시에서 현재 도시로 이동하는 거리는 0으로 초기화 합니다.
   • Integer.MAX_VALUE로 초기화 하지 않는 이유는 나중에 연산에서 오버플로가 발생합니다.
2. 도시간의 거리 가중치를 입력으로 받을 때 거리 배열에 값을 담아줍니다.
3. 3중 for문을 통해 A → C, A → B B → C 거리를 비교합니다.
   • 즉, 현재 발견된 거리가 다른 정점을 경유해서 가는 거리보다 멀다면 새로 갱신합니다.

📌 입력

        int[][] D = new int[N][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] = INF;
            }
        }

        StringTokenizer st;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            D[a][b] = D[a][b] > w ? w : D[a][b];
        }

발견된 최단 거리 배열 D를 선언하고 초기화해줍니다.

그리고 입력으로 각 도시간의 간선과 가중치를 입력받습니다.

이때 이미 입력으로 받은 가중치보다 큰 가중치인 간선이 발견되면 입력하지 않습니다.

📌 플로이드-워셜

        for(int k = 1; k<N; k++){
            for(int i =1; i<N; i++){
                for(int j=1; j<N; j++){
                    if(D[i][j] > D[i][k] + D[k][j]){
                        D[i][j] = D[i][k] + D[k][j];
                    }
                }
            }
        }

k : 경유지를 의미합니다.

i : 출발지를 의미합니다.

j : 목적지를 의미합니다.

현재 출발지로부터 목적지까지의 거리 D[i][j]가 경유지 k도시를 경유해서가는 D[i][k] + D[k][j]보다 크다면 거리를 갱신해줍니다.

• i → j 최단 거리가, i → k k → j로 돌아가는 거리보다 크다면 갱신해준다는 의미입니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static final int INF = 100000001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N =Integer.parseInt(br.readLine())+1;
        int M = Integer.parseInt(br.readLine());

        int[][] D = new int[N][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] = INF;
            }
        }

        StringTokenizer st;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            D[a][b] = D[a][b] > w ? w : D[a][b];
        }

        for(int k = 1; k<N; k++){
            for(int i =1; i<N; i++){
                for(int j=1; j<N; j++){
                    if(D[i][j] > D[i][k] + D[k][j]){
                        D[i][j] = D[i][k] + D[k][j];
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<N; i++){
            for(int j=1; j<N; j++){
                sb.append(D[i][j] != INF ? D[i][j] : 0).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

    }
}

결과