플로이드-워셜(Floyd-Warshall) 알고리즘

플로이드-워셜 알고리즘

1. 가중치 그래프에서 만들 수 있는 모든 두 정점 사이의 최단 거리를 구하는 알고리즘이다.
2.  이 그래프를 사용하기 위해선 가중치가 음이 아니여야 한다.(음수이면 무한정으로 음수를 더함)
3. 플로이드 워셜 알고리즘은 최단 거리를 구하기 위해 동적 프로그래밍 방식을 사용한다.

 

 

 

먼저 그래프에서 모든 노드로 가는 최단 거리를 2차원 배열로 만든다. 이때 자기 자신(1 -> 1)으로 가는 최단 거리는 0이다. 또한 갈수 없는 노드는 무한으로 표현한다. 프로그램에서는 무한대 표현이 불가능함으로 무한대를 나타낼 수 있는 충분히 큰 수로 대체한다. 2차원 배열을 모든 정점의 개수가 n개일 때 n * n형태의 배열이 만들어진다.

 

	1	2	3	4	5
1	0	1	3	-	-
2	1	0	4	7	-
3	3	4	0	-	2
4	-	7	-	0	5
5	-	-	2	5	0

 

이제 여기서부터 다음과 같은 방법으로 표를 갱신해나간다.

1. i부터 j까지 가는 최단 경로를  A[i][j]라고 하자.
2. A[i][j] > A[i][k] + A[k][j]이면  A[i][j] = A[i][k] + A[k][j]이다.
3. 2번 과정을 i , j, k가 모두 n(정점의 개수)가 될 때까지 반복한다.

위 과정을 프로그램으로 구현할 때는 반복문을 사용하는데 한눈에 보이질 않아서 다른 방식으로 표현을 해봤다.

 

각각의 화살표는 특정 노드에서 특정 노드로 가는 방법을 의미한다. 이는 두 노드 사이의 최단 거리를 의미하기도 한다. 그림에 표현된 i와 j, k를 모두 노드의 개수만큼 반복하면 된다. 예를 들어 i = 1, k = 2로 두고 j를 1부터 5까지 돌리면서 모든 경우의 수를 다 찾는다. 이렇게 찾는 과정에서 기존의 최단거리 배열보다 더 짧으면 값을 갱신한다. 이렇게하면 최단 거리로만 이루어진 배열을 얻을 수 있다.

 

이를 이용한 문제가 프로그래머스 합승 택시 요금 문제이다.

프로그래머스

코드는 다음과 같다.

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        
        int[][] node = new int [n + 1][n + 1];
        
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                node[i][j] = 20000001;
            }
            node[i][i] = 0;
        }
        
        for(int[] i: fares) {
            node[i[0]][i[1]] = i[2];
            node[i[1]][i[0]] = i[2];
        }
        
        for(int k = 1; k < n + 1; k++) {
            for(int i = 1; i < n + 1; i++) {
                for(int j = 1; j < n + 1; j++) {
                    if(node[i][j] > node[i][k] + node[k][j]) {
                        node[i][j] = node[i][k] + node[k][j];
                    }
                }
            }
        }
            
        int min = Integer.MAX_VALUE;
        for(int i = 1; i < n + 1; i++)
            min = Math.min(min, node[s][i] + node[i][a] + node[i][b]);
            
        
        return min;
    }
}

 

앞선 방식으로 배열은 만든 후 마지막에 s부터 i까지 그리고 i부터 a, i부터 b로 가는 최단 거리를 i를 바꿔가며 찾는다. 왜냐하면 i까지는 합승으로 가기 때문이다.

 

[참고자료]

https://www.programiz.com/dsa/floyd-warshall-algorithm