[백준 11404 : JAVA] 플로이드 / 플로이드 와샬

개요

 

문제 이름처럼 플로이드 와샬 알고리즘을 사용한다.

플로이드 와샬은 다익스트라, 벨만포드와 같이 간선의 가중치가 1이 아닌경우에 최단경로를 찾는데 사용된다.

 

각각의 특징을 짧게 나마 정리하면,

 

다익스트라 -  한 노드 ▶ 모든 노드 / 빠름 / 가중치가 음수이면 구할 수 없다.

벨만 포드 - 한 노드 ▶ 모든 노드 / 중간 / 가중치가 음수일 때 다익스트라 대신 사용할 수 있다.

플로이드 와샬 - 모든 노드 ▶ 모든 노드 / 느림 / 가중치가 음수여도 사용할 수 있다.

 

각 알고리즘 문제를 풀어보며 생각되는 가장 간단한 특징들이다.

 

문제를 보면 모든노드 ▶ 모든 노드로 가는 최단 경로를 구하라는 것을 알 수 있다.

그러므로 플로이드 와샬 알고리즘을 구현하도록 한다.

 

문제

 

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

 

풀이

 

INF는 무한대를 의미하며 동시에 경로가 없다는 것을 뜻한다.

 

INF는 가능한 최대 거리보다 큰 값을 잡아야 한다.

 

최대 값은 |v - 1| * maxLength 이므로 아래 코드와 같이 INF 값을 설정하였다.

(maxLength는 최대 버스 비용을 뜻한다.)

 

플로이드 와샬은 아래와 같이 3중 for문으로 구현을 하는데

 

for(i = 1 -> n)

     for(j = 1 -> n)

          for(k = 1 -> n)

 

예를 들어 n = 3인 경우

 

i, j, k  ▶ 1, 1, 1  →  1출발 1경유 1도착

i, j, k  ▶ 1, 1, 2  →  1출발 1경유 2도착

i, j, k  ▶ 1, 1, 3  →  1출발 1경유 3도착

i, j, k  ▶ 1, 2, 1  →  2출발 1경유 1도착

i, j, k  ▶ 1, 2, 2  →  2출발 1경유 2도착

i, j, k  ▶ 1, 2, 3  →  2출발 1경유 3도착

i, j, k  ▶ 1, 3, 1  →  3출발 1경유 1도착

i, j, k  ▶ 1, 3, 2  →  3출발 1경유 2도착

i, j, k  ▶ 1, 3, 1  →  3출발 1경유 3도착

 

i, j, k  ▶ 2, 1, 1  →  1출발 2경유 1도착

i, j, k  ▶ 2, 1, 2  →  1출발 2경유 2도착

i, j, k  ▶ 2, 1, 3  →  1출발 2경유 3도착

i, j, k  ▶ 2, 2, 1  →  2출발 2경유 1도착

i, j, k  ▶ 2, 2, 2  →  2출발 2경유 2도착

i, j, k  ▶ 2, 2, 3  →  2출발 2경유 3도착

i, j, k  ▶ 2, 3, 1  →  3출발 2경유 1도착

i, j, k  ▶ 2, 3, 2  →  3출발 2경유 2도착

i, j, k  ▶ 2, 3, 1  →  3출발 2경유 3도착

 

i, j, k  ▶ 3, 1, 1  →  1출발 3경유 1도착

i, j, k  ▶ 3, 1, 2  →  1출발 3경유 2도착

i, j, k  ▶ 3, 1, 3  →  1출발 3경유 3도착

i, j, k  ▶ 3, 2, 1  →  2출발 3경유 1도착

i, j, k  ▶ 3, 2, 2  →  2출발 3경유 2도착

i, j, k  ▶ 3, 2, 3  →  2출발 3경유 3도착

i, j, k  ▶ 3, 3, 1  →  3출발 3경유 1도착

i, j, k  ▶ 3, 3, 2  →  3출발 3경유 2도착

i, j, k  ▶ 3, 3, 3  →  3출발 3경유 3도착

 

빨간색의 경우 확인하지 않아도 되어서 조건을 걸어주었다.

사실 조건을 안걸어줘도 정답을 잘 나온다. 

 

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 100 * 100_000;
    static int n, m;
    static int arr[][];

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];

        // 입력받은 값으로 변수 초기화
        init();
        // 플로이드 와샬 알고리즘
        floydWarshall();

        // 출력을 위한 객체
        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                // 무한대가 저장되어 있으면 경로가 없다는 의미이므로
                // 0을 출력한다.
                sb.append((arr[i][j] != INF ? arr[i][j] : 0) + " ");
            }
            sb.append("\n");
        }
        bw.write(sb.toString());

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

    private static void init() throws IOException {
        for(int i = 0 ; i <= n; i++)
            Arrays.fill(arr[i], INF);

        // 자기 자신으로 가는 경로 0으로 초기화
        for(int i = 1; i <= n; i++)
            arr[i][i] = 0;

        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());

            // 기존의 값보다 작은 값이 들어오면 갱신해준다.
            arr[start][end] = Math.min(cost, arr[start][end]);
        }
    }

    private static void floydWarshall() {
        // 경유 노드
        for(int i = 1; i <= n; i++){
            // 시작 노드
            for(int j = 1; j <= n; j++){
                // 시작 노드 != 경유 노드
                if(i != j) {
                    // 도착 노드
                    for (int k = 1; k <= n; k++) {
                        // 시작노드 != 도착노드 && 도착노드 != 경유노드
                        if(j != k && i != k){
                            // 기존의 값 보다 경유한 값이 작은 경우
                            if(arr[j][k] > arr[j][i] + arr[i][k]){
                                arr[j][k] = arr[j][i] + arr[i][k];
                            }
                        }
                    }
                }
            }
        }
    }
}