[ 개념 ] 39. 플로이드 와샬(Floyd-Warshall) 알고리즘

> 플로이드 와샬 알고리즘

Floyd-Warshall algorithm

앞의 두 최단거리 알고리즘과는 다르게 정점 V개가 있고 거리가 다 주어져 있을 때, 단 한번의 시행으로 모든 정점 쌍 사이의 거리를 다 구해낸다.

코드는 굉장히 짧은데, 아주 전형적인 3중 for문의 형태를 하고 있고 O(V^3)입니다.

음의 가중치가 있는 간선 그래프에서도 제대로 동작합니다.

-BOJ[11404] : 플로이드

이 문제를 풀 겁니다. 아니 제목부터 대놓고 플로이드입니다. 그러므로 플로이드를 씁시다.

각 정점 u, v 쌍에 대해 u에서 v로 가는 최단 경로를 한 번에 다 구할 것이고, 이를 위해 먼저 2차원 배열 dist를 준비합니다.

초기에는 자기 자신으로 가는 dist[i][i] 꼴은 다 0이고, 나머지는 ∞으로 설정해놓고 시작합니다.

이때, dist[i][i]=0이라는 것은 자기 자신으로 이동이 가능하다는 의미인데, 문제에 따라 기본적으로 이게 안 될 수도 있고 그때는 dist[i][i]도 ∞로 초기화합니다.

그리고 간선 정보를 받아서 u->v로 가는 거리가 w라면 dist[u][v] = w로 갱신합니다.

혹시라도 똑같은 u, v 쌍에 대해 서로 다른 w가 두 번 이상 들어올 수 있는데 이때는 그 중 가장 작은 것으로 갱신해야 합니다.

여기까지가 전처리에 해당하는 그래프 모델링이고, 이제 이 dist 배열만을 갖고 플로이드 알고리즘을 적용할 겁니다.

플로이드는 최단경로를 DP 형태의 문제로 정의하고 풀어냅니다.

shortestPath(i, j, k)라는 문제는 i번 정점에서 j번 정점까지, 1~k번 정점만 사용할 때의 최단 거리를 구하라는 의미입니다.

k단계 문제를 풀려면 k-1단계의 정보가 필요한데, 그래서 k=1~N까지 시도하며 정보를 계속해서 갱신하게 됩니다.

이때, k-1단계 이전의 정보는 더이상 필요하지 않아서 3차원 배열을 쓰지 않고 슬라이딩 윈도우 기법을 적용하여 덮어써서 2차원 배열 dist만 가지고도 해결이 됩니다.

이걸 저번의 벨만 포드 알고리즘과 비슷하게 k번의 루프를 돌려보면 마지막엔 더 이상 갱신되지 않는 최단 경로 배열 dist가 완성되는 겁니다.

매 단계마다 하는 일은 이러합니다.

이번이 k단계, 즉 1~k번 정점을 사용하여 도달가능한 최단거리를 구해야 하는 단계라 합시다.

그렇다면 지금까지 dist 배열에는 1~k-1번 정점만 사용해서 나올 수 있는 최단거리가 남아있죠.

이걸 사용해서 갱신합니다.

어떤 두 정점 i, j에 대해, k번 정점을 사용해 우회하면 지금까지보다 최단거리가 짧아지는가?

이 질문을 모든 i, j 쌍에 대해 던져보고 만약 그렇다면 갱신하는 것인데요. 이 쿼리의 형태는

if( dist[i][j] > dist[i][k] + dist[k][j] )

이런 형태가 됩니다. 현재 dist[i][j]는 지금까지 찾은 최단거리를 담고 있는데,

여기서 dist[i][k]+dist[k][j], 즉 k번 정점을 새로 우회하여 가는 경로가 더 빠를 수도 있는데 그걸 묻고 있는 겁니다.

만약 더 빠르다면, 이제 dist[i][j]는 dist[i][k]+dist[k][j] 값으로 갱신되어 더 작아집니다.

#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1000000000; // 절대 나올 수 없는 경로값

int main(){
    int N, M, dist[100][100];
    scanf("%d %d", &N, &M);
    // dist 배열 초기화
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            dist[i][j] = i==j ? 0 : INF;
    // 간선 정보 입력받음
    for(int i=0; i<M; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        dist[a-1][b-1] = min(dist[a-1][b-1], c);

    // 플로이드 와샬 알고리즘 적용
    for(int k=0; k<N; k++)
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);

    // 이제 dist 배열은 실제 최단 경로를 담고 있음
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++)
            printf("%d ", dist[i][j]);
        puts("");
    }
}

이게 위 문제를 푸는 소스 코드인데...

실제로 그래프가 마련되어 있을 때 플로이드 알고리즘은 20~23번 줄, 단 4줄밖에 안됩니다...

엄청 짧죠. 외워지기도 제일 빨리 외워지는 알고리즘입니다.

이게 끝나면 dist 배열의 i행 j열엔 말 그대로, i->j로 가는 최단 거리가 남게 됩니다!!

정점 V개에 대해 모든 정점에서 다익스트라 알고리즘을 돌리면 O(V(E+VlogV))일 것이고

만약 간선 개수가 V^2보다 많이 작다면 다익스트라 알고리즘이 약간 우위지만

음의 가중치를 가진 그래프에서는 이건 사용이 불가능하고,

벨만 포드 알고리즘을 모든 정점에 대해 돌리면 O(V^2*E)이니 이쪽은 플로이드가 거의 무조건 우위입니다.

모든 정점 간의 거리를 빠르게 구해야 할 땐 플로이드가 최고지요.

또한 그 코드의 간단함과 목적의 명확함 때문에, 어려운 문제들은 이게 최단경로 문제인가조차 처음엔 알 수 없게 포장되어 나오기도 합니다.

플로이드 관련 문제

추천 문제

11404번: 플로이드

위에서 설명한 문제입니다.

11403번: 경로 찾기

위에서 설명한 문제입니다.

1389번: 케빈 베이컨의 6단계 법칙

문제 설명이 좀 길지만, 그냥 자기 자신으로부터 다른 모든 정점으로의 각 최단거리 합이 가장 작은 애를 하나 찾으라는 문제입니다.

1613번: 역사

a가 b보다 먼저 일어났다고 할 때 dist[a][b] = 1, 나머지는 ∞인 상태로 플로이드를 돌립니다.

이러면 끝나고 나서도 dist[u][v] = ∞, dist[v][u] = ∞이면 u, v는 서로 전후관계를 알 수 없다는 말입니다.

만약 dist[u][v]가 무한대가 아니라면 u에서 v로 가는 경로가 존재한다는 것이고, 따라서 u가 v보다 먼저 일어났다는 걸 알 수 있습니다.

u가 v보다 나중에 일어났다는 것을 확인하려면 반대로 dist[v][u]를 확인하면 됩니다.

2610번: 회의준비

위원회의 수는 컴포넌트의 수이고, 각 컴포넌트마다 안에서 대표를 뽑아야 하는데 이 대표는 컴포넌트 안의 다른 정점들로의 최단거리 중 최댓값이 가장 작은 사람이겠죠.

따라서 각 정점을 컴포넌트별로 분리하는 작업도 필요합니다.

1956번: 운동

간단하죠. dist[i][i]도 다 ∞인 상태로 시작하여 플로이드를 돌리고

마지막에 dist[i][i]가 최소인 i를 찾고 그 값을 출력하면 됩니다.

13168번: 내일로 여행 (★)

입력 데이터만으로도 책을 쓸 정도로 입력이 길지만, 시크하게 map 등으로 문자열을 정점 번호로 대응시킨 후 넘어갑시다.

그럼 이 문제는 a->b->c->...->a 형태의 고정된 경로의 최단비용이므로, 각 경로의 최단비용을 다 답해야 하니까 아예 모든 경로의 최단비용을 구해놓는 플로이드가 매우 적합하지요.

티켓을 샀을 때와 사지 않았을 때 몇몇 간선의 cost를 달리하면서, 둘 중 어느 쪽이 좋은지 결과를 놓고 비교하면 됩니다.

9205번: 맥주 마시면서 걸어가기 (★)

각 편의점에 들를 때마다 무조건 맥주를 풀로 조달해간다면, 출발해서 다른 정점까지 1000미터 이하의 거리라면 그 정점으로는 갈 수 있습니다.

따라서 출발점, 도착점 정점을 추가로 만들고, 거리가 1000 이하인 정점들 사이에만 간선을 놓고, 출발점에서 도착점까지 이동 가능한지를 판별하면 됩니다.

2458번: 키 순서 (★)

u보다 v가 키가 클 때 dist[u][v] = 1이고 나머지는 ∞인 상태로 시작해서,

마지막에 자신을 제외한 모든 정점에 대해 자신이 그 정점으로 갈 수 있거나 그 정점에서 자신으로 갈 수 있는 정점 수를 세면 됩니다.

u에서 v로 갈 수 있다면 u보다 v가 확실히 크다는 것이고, 반대방향은 v보다 u가 확실히 키가 작다는 정보를 주기 때문입니다.

둘 다 아니라면 u, v의 키 관계를 알 수 없게 됩니다.

11562번: 백양로 브레이크 (★)

알고스팟 등의 문제를 풀어봤다면 이 문제도 쉽게 풀 수 있습니다. 아마...

건물 s에서 건물 e로 갈 때 양방향으로 바꿔야 하는 길의 최소 개수란, 현재 그래프에서 거쳐야 하는 역방향 간선의 최소 개수를 말하겠죠.

따라서 (u->v)로 가는 길이 존재하고 그 길이 양방향이라면 dist[u][v] = dist[v][u] = 0, 아니라면 dist[u][v]만 0이고 dist[v][u]는 1로 두면 됩니다. 역방향으로 v에서 u로 가려면 이 길을 양방향으로 바꿔야 하니까요.

1507번: 궁금한 민호 (★)

플로이드가 최단경로를 갱신하는 방법을 반대로 이용하면 됩니다.

만약 dist[i][j] = dist[i][k] + dist[k][j]라면, 어차피 i->k->j로 우회해 간 거리가 원래의 최단거리이므로 i->j로 바로 가는 간선을 지워버려도 됩니다.

이렇게 해서 간선을 지울 수 있는 만큼 모두 지우는데, 만약 중간에 dist[i][j]보다 dist[i][k] + dist[k][j]가 더 작은 경우가 존재할 경우 모순입니다.

 

출처 : blog.naver.com/kks227/220796963742