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

플로이드-워셜(Floyd-Warshall) 알고리즘은 "모든 정점에서 모든 정점으로의 최단 경로"를 구하는 알고리즘이다.

핵심 아이디어는 '경유지'에 있다.

핵심 원리

임의의 두 정점 i에서 j로 가는 최단 거리를 구할 때, 중간에 다른 정점 k를 거쳐서 가는 경우와 직접 가는 경우를 비교하며 더 짧은 거리로 갱신한다.

$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$

알고리즘 동작 과정

1. 초기화

인접 행렬을 만든다. 자기 자신으로 가는 거리는 0, 연결된 간선은 가중치, 연결되지 않은 간선은 INF로 설정한다.

(INF는 보통 1,000,000,000이나 적당히 큰 값을 사용해 오버플로우를 방지한다.)

2. 경유지 선택

정점 1부터 N까지 하나씩 경유지(k)로 잡는다.

3. 최단 거리 갱신

선택된 k를 거쳐가는 것이 기존 $dist[i][j]$보다 작으면 값을 바꾼다.

4. 반복

모든 정점을 경유지로 한 번씩 다 사용하면 종료한다.

특징 및 주의사항

• 시간 복잡도: $O(N^3)$이다. 정점 개수 N이 400~500을 넘어가면 사용하기 어렵다.

• 공간 복잡도: $O(N^2)$이다. $N*N$ 크기의 2차원 배열이 필요하다.

• 음수 가중치: 다익스트라와 달리 음수 가중치가 있어도 동작한다. 다만, 음수 사이클이 있으면 최단 거리를 구할 수 없다.

음수 가중치와 음수 사이클

• 단순 음수 가중치: 최단 거리가 음수가 나올 수 있으며, 이는 정상이다. (단순히 비용이 싼 경로)

• 음수 사이클: 한 바퀴 돌아 제자리로 왔을 때 총합이 음수인 경우이다.

• 판별법: 알고리즘 종료 후, 자기 자신으로의 거리가 0보다 작은 음수라면 해당 그래프에는 음수 사이클이 존재하는 것이다.

// 3중 포문이 다 돌고 난 후
for (int i = 1; i <= n; i++) {
    if (dist[i][i] < 0) {
        // 하나라도 0보다 작은 게 발견되면 음수 사이클이 존재하는 그래프!
        System.out.println("음수 사이클 발생!");
        return; 
    }
}

문제

프로그래머스 순위

풀이

이 문제는 '거리'가 아니라 '승패 관계'라는 논리 전파에 플로이드-워셜을 응용했다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        boolean[][] win = new boolean[n+1][n+1];
        
        for(int i=0; i<results.length; i++){
            win[results[i][0]][results[i][1]] = true;
        }
        
        for(int k=1; k<=n; k++){       // k: 경유지 (반드시 제일 바깥!)
            for(int i=1; i<=n; i++){   // i: 출발지
                for(int j=1; j<=n; j++){ // j: 도착지
                    if(win[i][k] && win[k][j]) win[i][j] = true;
                }
            }
        }
        
        int cnt = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i == j) continue;
                if(win[i][j] || win[j][i]) cnt++; // 내가 이겼거나 졌거나 결과가 있으면 카운트
            }
            //본인 제외 결과가 전부 있으면 순위 확정 가능.
            if(cnt == n-1) answer++;
            cnt = 0;
        }
        
        return answer;
    }
}