[C++ 알고리즘] 플로이드 알고리즘

이 글은 플로이드 알고리즘을 학습하며 이렇게 짜면 왜 안될까?를 고민한 과정을 작성한 글입니다.
플로이드 알고리즘 자체가 처음이라면 아래 링크에서 플로이드 알고리즘에 대한 개념을 익힌 후 글을 읽으시는 것을 추천합니다.

https://blog.encrypted.gg/1035

[실전 알고리즘] 0x1C강 - 플로이드 알고리즘

 

최단거리

플로이드 알고리즘은 그래프의 모든 정점간의 최단거리를 구하는 알고리즘이다. 구현하는 방법은 간단한 편이다.

1. NxN크기의 배열을 큰 값(INF)으로 초기화한다.
2. 각 정점간의 거리를 입력받으며 배열을 채워나간다.
3. 모든 정점에 대해 다른 정점을 거쳐서 가는 경우를 검사한다. 만일 다른 정점을 거쳐가것이 최단거리라면 값을 갱신한다.

그래서 코드를 보면 아래와 같은 식이다.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 100000001; //정점이 최대 100개고 정점간 최대 길이는 100000이니 100000*(100-1)보다 큰 값으로 설정
using namespace std;

int arr[101][101];


int main(){
    int N,M;

    cin>>N>>M;

    for(int i=1;i<=N;i+)fill(&arr[0],&arr[0]+N,INF);

    int a,b,cost;
    while(M--){
        cin>>a>>b>>cost;
        arr[a][b]=min(arr[a][b],c);
    }

    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]); //i-j로 이동하는 것과 i-k,k-j로 이동하는 거리 중 작은 값
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
	        if(arr[i][j]==INF)cout<<"X ";
            else cout<<arr[i][j]<<" ";
        }
        cout<<"\n";
    }
}

나는 처음에 개념만 보고 직접 코드를 짜봤는데 지금처럼 k i j 순으로 반복문을 짠 것이 아니라 i j k순으로 반복문을 짰었다. 당연히 이렇게 하면 결과가 다르게 나오는데, 반례는 아래와 같다. 

5
6
1 2 2
2 4 2
1 4 1
3 4 1
4 5 3
5 1 7

그림상에서는 2-4-5-1을 통해 2에서 1로 도달할 수 있지만 위와 같이 반복문을 돌리면 2에서 1에 갈 수 없다며 X가 출력된다. 그 이유는 2에서 5로 가는 경로값 5는 k=4, i=2, j=5일때 업데이트 되기 때문에, 2에서 1로 가는 경로가 업데이트 되어야하는 시점인 k=5, i=2, j=1일 때는 arr[2][5]값이 INF이기 때문이다. 그렇기에 2에서 1로 도달할 수 없다고 판단해버린다.

경로추적

그리고 경로를 추적하는 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 100000001; //정점이 최대 100개고 정점간 최대 길이는 100000이니 100000*(100-1)보다 큰 값으로 설정
using namespace std;

int arr[101][101];
int nxt[101][101]; //추가된 부분1


int main(){
    int N,M;

    cin>>N>>M;

    for(int i=1;i<=N;i+)fill(&arr[0],&arr[0]+N,INF);

    int a,b,cost;
    while(M--){
        cin>>a>>b>>cost;
        arr[a][b]=min(arr[a][b],c);
        nxt[a][b]=b; //추가된 부분2
    }

    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(arr[i][j]>arr[i][k]+arr[k][j]){
                    arr[i][j]=arr[i][k]+arr[k][j];
                    nxt[i][j]=nxt[i][k]; //추가된 부분3
                }
            }
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
	        if(arr[i][j]==INF)cout<<"X ";
            else cout<<arr[i][j]<<" ";
        }
        cout<<"\n";
    }

    cout<<"경로 출력\n"
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(arr[i][j]==0||arr[i][j]==INF)cout<<"0 ";
            vector<int> path;
            int next=i;
            while(next!=j){
                path.push_back(next);
                next=nxt[next][j];
            }
            path.push_back(next);
            
            cout<<path.size()<<" ";
            for(int i=0;i<path.size();i++){
                cout<<path[i]<<" ";
            }
        }
        cout<<"\n";
    }
}

나는 추가된 부분 3의 nxt배열을 갱신하는 부분을 처음에 k로 짜고 왜 문제가 되는지 몰랐었다.

nxt[i][j]=nxt[i][k]; //추가된 부분3

nxt[i][j]=k; //잘못짰던 부분

중간에 거쳐가는 노드가 2개 이상부터는 nxt배열을 k로 갱신했을 때 문제가 생긴다. 

예를 들어 아래와 같은 그래프가 있다고 하자.

그러면 우리가 기대하는 nxt표는 아래와 같이 생겼을 것이다.

하지만 nxt를 갱신할 때 k로 한다면 nxt표는 아래와 같이 나온다.

이 이유를 알기 위해서는 플로이드 알고리즘이 어떻게 동작하고 표가 어떻게 갱신되는지를 살펴봐야 한다.

먼저 1-3으로 가는 값은 최초에는 INF로 기록되어 있을 것이다. 직접적으로 연결되어 있지 않기 때문이다. 이 값이 갱신되는 것은 중간노드(k) 2, 출발노드(i) 1, 도착노드(j) 3일때 일 것이다.

그렇다면 1-4로 가는 경로는 언제 갱신될까? 1-4로 가는 경로는 중간노드(k) 3, 출발노드(i) 1, 도착노드(j) 4일때 갱신된다. 그런데 nxt배열은 1-4로 최단경로로 가기 위해 다음으로 가야 할 노드를 기록하는 배열이기 때문에 k값인 3이 아니라 nxt(1)(3), 즉 3을 거치기 위해 다음으로 가야 할 노드를 기록해야 한다. 그렇기에 nxt(i)(k)값을 기록하는 것이다.

처음에는 중간노드(k) 2, 출발노드(i) 1, 도착노드(j) 4일때 갱신되는게 아닐까 하고 생각했지만 갱신 조건을 보면 아래와 같다.

for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(arr[i][j]>arr[i][k]+arr[k][j]){
                    arr[i][j]=arr[i][k]+arr[k][j];
                    nxt[i][j]=nxt[i][k]; //추가된 부분3
                }
            }
        }
    }

k=2, i=1, j=4일 때에는 arr(1)(4) = INF, arr(i)(k)=1, arr(k)(j)=INF이기 때문에 값이 갱신되지 않는다. (arr(2)(4)는 k가 3일때 갱신되니 아직 INF일 시점이다.)

그림을 보면 알겠지만 1에서 4로 가기 위해 3으로 간다고 경로를 기록해버리면 2를 생략하게 된다.

관련 문제

관련 문제는 백준에서 풀어볼 수 있다.

https://www.acmicpc.net/problem/11404

https://www.acmicpc.net/problem/11780