[알고리즘] Floyd-Warshall 플로이드-와샬 알아보기 ( 백준 11404번 경로 찾기 with 자바 )

 

🤔 Floyd-Warshall 플로이드-와샬 알고리즘?

그래프에 있는 모든 정점에 대해 각 정점들이 다른 정점들까지 도달하기 위해 필요한 모든 최단 거리를 구할때 사용합니다.

플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행하는 특징이 있습니다.

 

즉, 정점 A, 정점B 까지의 최단 거리를 구하기 위해 중간에서 거쳐갈 수 있는 모든 정점들을 확인해보고 그 중 최단 거리의 경로를 찾습니다.

 

(플로이드 와샬은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬로 표현하여 최단 거리를 계산합니다.)

 

 

✔ 시간복잡도

3중 for문을 통해 거쳐가는 정점을 이용하여 그래프를 탐색하기 때문에 O(n^3)의 시간복잡도를 갖습니다.

 

 

✔ 탐색 방법

문제와 함께 플로이드-와샬 알고리즘의 탐색방법을 살펴보겠습니다.

 

백준 11404번 플로이드 

난이도 : 골드 🥇

11404번: 플로이드

 

 

위 예제를 그래프로 표현하면 옆의 그림처럼 표한할 수 있습니다.

각 정점들은 도시이고 화살표의 숫자는 도시에서 다른 도시로 가기위한 비용입니다.

문제는 모든 도시의 쌍에 대해서 도시A에서 B로 가는데 필요한 최소 비용을 구해야 합니다.

플로이드-와샬 알고리즘은  모든 정점에 대해 각 정점들이 다른 정점들까지 도달하기 위해 필요한 모든 최단 거리를 구할때 사용합니다.

즉, 이 문제 풀이에 적용해볼 수 있겠습니다.

 

 

각 정점에서 다른 정점까지의 최소 비용을 이차원 배열의 형태로 표현하면 아래와 같이 표현할 수 있습니다.

( 0은 자기 자신(A, A)이기 때문에 비용이 0원 입니다, X 는 연결되지 않아 갈 수 없는 부분입니다 )

0	2	3	1	10
X	0	X	2	X
8	X	0	1	1
X	X	X	0	3
7	4	X	X	0

		int n = Integer.parseInt(br.readLine()); // 5 도시의 수
        int m = Integer.parseInt(br.readLine()); // 14 도시와 연결된 경로의 수
        int x = 100000 * (n-1) + 1;
        int[][] city = new int[n + 1][n + 1];
        
        // 초기 이차원 배열 전체를 x와 0원인 부분은 0이 되도록 세팅해줍니다.
        for (int i = 1; i < city.length; i++) {
            for( int j = 1; j<city[i].length; j++){
                city[i][j] = x;
                if( i == j ){
                    city[i][j] = 0;
                }
            }
        }
        
		// 최소 비용을 구하기 때문에 가장 적은 비용으로 세팅합니다.
        // 이렇게까지 하면 위의 표처럼 이차원 배열을 세팅하였습니다.
        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 cost = Integer.parseInt(st.nextToken());

            city[a][b] = Math.min(city[a][b], cost);
        }

 

📌  연결되지 않은 X의 값 설정

최대값(무한)을 생각해서 Integer.MAX_VALUE를 설정해 보았지만 다른 경로의 비용과 합쳐지게 되면 음수가 되어 오류가 발생합니다 😭

 

int x = 100000 * ( n - 1 ) + 1
비용(연결된 간선의 가중치) 의 최대값 * 간선의 수(=노드의 수  - 1 ) 보다 커야하기 때문에 + 1

 

경로가 없는 부분을 최대값(무한)으로 설정하는 이유는 실제 경로가 존재하지 않음을 나타내기 위함입니다.
예를들어 1->2->3->4->5 처럼 모든 경로를 거쳐서 도착한 비용은
비용 * 간선의 수 로 표현할 수 있습니다 하지만 만약 경로가 없는 x가 모든 경로를 거친 비용보다 작다면 플로이드-와샬 알고리즘은 경로가 없는 x의 값으로 비용을 세팅하게되어 알고리즘의 오류로 이어지게 됩니다.

 

 

세팅된 이차원 배열에 프로이드-와샬 알고리즘을 사용하여 최소 비용을 탐색합니다.

for( int k = 1; k<=n; k++){          // k : 거쳐가는 도시
    for( int i = 1; i<=n; i++){      // i : 도시A
        for( int j = 1; j<=n; j++){  // j : 도시B
            if( i != j){
                city[i][j] = Math.min(city[i][j], city[i][k] + city[k][j]);
            }
        }
    }
}

 

경로가 있을 경우 ( 예 : k = 1, i = 3, j = 4 )

city[3][4] 3(i)에서 4(j)를 바로 가는 경우 vs city[i][k] + city[k][j]  3(i)에서1(k)을 거쳐 4(j)로 가는 경우를 비교하여  더 적은 비용을 세팅합니다. ( 1로 세팅 )

 

경로가 없을 경우 ( 예 : k = 2, i = 4, j = 5 )

city[i][j] = 3 vs city[i][k] + city[k][j] = X + X

경로가 없을경우 X를 더하게 됨으로 바로 가는 경로가 있다면 당연히 거쳐가는 경로보다 작기 때문에 바로 가는 경로가 세팅되어집니다 ( 3으로 세팅 )

 

이처럼 바로 가는 경로와, 거쳐가는 경로를 모두 비교하면서 각 정점과의 최소 비용(또는 최단 거리)를 이차원 배열로 나타낼 수 있게됩니다.

 

 

🔎 전체 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.lang.StringBuilder;

public class Main{
	public static void main(String[] args) throws IOException {
       	BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
	    StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int x = 100000 * (n-1) + 1;
        int[][] city = new int[n + 1][n + 1];
        for (int i = 1; i < city.length; i++) {
            for( int j = 1; j<city[i].length; j++){
                city[i][j] = x;
                if( i == j){
                    city[i][j] = 0;
                }
            }
        }

        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 cost = Integer.parseInt(st.nextToken());

            city[a][b] = Math.min(city[a][b], cost);
        }


        for( int k = 1; k<=n; k++){
            for( int i = 1; i<=n; i++){
                for( int j = 1; j<=n; j++){
                    if( i != j){
                        city[i][j] = Math.min(city[i][j], city[i][k] + city[k][j]);
                    }
                }
            }
        }

        for( int i = 1; i<=n; i++){
            for (int j = 1; j <= n; j++) {
                if (city[i][j] == x) {
                    city[i][j] = 0;
                }
                sb.append(city[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
        

        br.close();
	}
}