[알고리즘] 최단 거리 알고리즘 - 플로이드, 백준 11404 C++ 풀이까지

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

바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.

---

위의 그래프에서 직접 연결된 간선에 한해, 첫 단계의 최단 거리를 구해보자.

굉장히 쉽게 구할 수 있다. 

 

1에서 1로 가는 거리는 당연하게도 0이고 1에서 2는 바로 갈 수 있기에 그 가중치인 4를 적어주면 된다. 3에서 5의 경우 4를 거쳐서 간다면 8로 갈 수 있지만 현재는 하나의 간선만 고려하기에, 즉 바로 갈 수 있는 경로만 고려하기에 15로 구해진다.

 

플로이드 알고리즘은 여기서 일단 정점 한 개를 더 거쳐서 갱신할 수 있는 최단 거리를 계산하는 알고리즘이다.

 

즉, D[s][t]에 대해 D[s][t] / D[s][u] + D[u][t]를 비교하는 방식이며, u를 1~n 까지 모든 정점에 대해 반복하면 된다.

 

두 번째 단계의 테이블은 1번 정점을 거쳐서 갱신할 수 있는 거리는 갱신해버리면 된다.

예를 들어 3->2를 생각해보면, 기존 무한대에서 1을 거치는 5로 업데이트 되었다.

---

 

바로 문제로 구현해보자.

간단하게 삼중 for문을 때려버려도 된다.

 

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

 

/** 최단거리 11404 플로이드 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
int dist[105][105];
const int INF = 0x3f3f3f3f;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        fill(dist[i], dist[i] + n + 1, INF);

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);
    }

    for (int i = 1; i <= n; i++)
        dist[i][i] = 0;

    // k번째 원소가 중간에 거치는 원소
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] == INF)
                cout << "0 ";
            else
                cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }
}

 

구현 시 주의사항

1. INF는 0x7f7f7f7f로 int형의 최대 값으로 선언하게 되면, 두 INF를 더하는 과정에서 오버플로우가 생긴다.
2. 삼중 for 문에서 당연하게도 중간에 거쳐갈 노드 k는 가장 바깥으로 빼야 한다.
3. adj를 인접행렬로 선언하면 바로 최단 거리 저장용 테이블로 사용할 수 있다.

---

경로 복원

a에서 b까지 최단 거리로 가려면 a에서 어느 정점으로 가야하는지 저장해야 하는데, 이를 nxt 테이블이라 하자.

nxt 테이블은 최단 거리 테이블을 채우면서 같이 채울 수 있다. 

먼저 아무 정점도 거치지 않는 첫 단계를 생각해보자.

 

최단 거리 테이블에 2->1 경로를 저장했고, 해당 경로의 중간에 거친 노드는 nxt 테이블의 [2][1]에 1로 저장되어 있다.

 

다음 단계부터가 중요하다. 다음 단계는 1번 노드를 거치는 최단 거리를 계산하는 단계인데, 2->3을 생각해보면 2->1->3이 최단거리이므로 nxt 테이블에는 nxt[2][3]=1이 저장되면 될 것이다. 그대로 채워보자.

 

여기서 1이 저장되는 이유는 1번 노드를 방문하는 단계니까 1을 넣는 것이 아니다. nxt[s][t]를 nxt[s][1]로 대체하는 것이다. 왜인지는 다음 단계에서 더 자세히 보자.

 

그 다음 두 번째 단계는 2번 노드도 거치는 경우이다.

이번에 신경써야 할 부분은 nxt를 2로만 채우는 것이 아니라, s->t 보다 s->2 + 2->t인 경우. 즉 이번 단계에서 갱신되는 노드에 대해 nxt[s][t]를 nxt[s][2]로 채워야 한다는 것이다.

nxt는 a에서 b로 갈 때 어느 정점으로 먼저 갈지를 저장하는 배열이다. 3->5를 생각해보자. 이번 단계에서 3->2, 2->5가 더 효율적임을 알아서 갱신했고, 이에 따라 nxt 배열 또한 3에서 5를 갈 때 어디로 먼저 가면 될까를 저장해야 한다.

저장될 값은 1일테고, 이를 구현적으로는 nxt[3][2]로 표현하면 된다. 3에서 5로 갈 때 가장 먼저 거쳐야 할 값은 3에서 2로 갈 때 거치는 값 = 1인 것이다. 바로 다음 단계도 보자.

3번 노드를 거치는 경우는 아무 일도 없어서 갱신이 없다. 다음도 보자.

 

이번에는 3->5가 특이하다. 이 전까지는 3->1->2->5가 최단 거리였고, nxt에는 1이 저장되어 있었다. 4번 노드를 거치게 되는 경우를 생각해봐도 3->1->4->5이므로 똑같이 nxt에도 1이 저장된다.

 

이제 nxt 배열은 다 구했고, 이를 바탕으로 경로를 복원하면 된다.

 

똑같이 3->5로 복원해보자.

nxt[3][5] = 1이다. 따라서 3 -> 1 경로는 자명하다.

그 다음은? 1에서 5까지 갈 때 그 다음에 갈 곳은 nxt[1][5]에 저장되어 있다. nxt[1][5]는 4이므로 3 -> 1 -> 4 까지는 구했고, 그 다음은 nxt[4][5] = 5로 3 -> 1 -> 4 -> 5의 경로 완성이다.

 

다시, 정리해보자면 nxt[i][j]는 i->j로 갈 때 가장 먼저 방문해야 할 곳이다. 따라서 k번째 노드를 경유하는게 더 최단 거리인 경우

nxt[i][j] = nxt[i][k]로 갱신하면 된다.

• 여기서 nxt[i][k]를 단순히 암기해서는 안된다. 무수한 알고리즘들을 외우는 방식은 코딩 테스트를 통과할 수 없고 원리를 이해해야 한다.
• nxt[i][j]는 i가 시작점이다. i -> ... -> k -> ... -> j 의 경로에서 i 바로 뒤에 위치한 노드는 nxt[i][k]로 구할 수 있기에 nxt[i][k]로 갱신하는 것이다.
• 케이스를 나눠서 좀 더 명확히 이해해보자.
  
  • 만약 i -> k 사이에 노드가 없다면 nxt[i][k] = k 일 것이다.
  • i -> u -> k 라면 nxt[i][k] = u 일텐데, 이 값은 언제 초기화되었을까? 가장 바깥쪽 loop, 즉 경유 노드가 u일 때 i -> k 경로를 구하면서 nxt[i][k] = u로 초기화되었다.

---

문제로 구현해보자.

 

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

 

구현은 크게 어려운 부분은 없다.

/** 최단거리 11404 플로이드 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
int dist[105][105];
int nxt[105][105];
const int INF = 0x3f3f3f3f;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        fill(dist[i], dist[i] + n + 1, INF);

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);
        // nxt도 초기화. 첫 단계이므로 a->b 간선이 있으면 nxt[a][b] = b
        nxt[a][b] = b;
    }

    for (int i = 1; i <= n; i++)
        dist[i][i] = 0;

    // k번째 원소가 중간에 거치는 원소
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                // k 번째 원소를 거치는 경우가 더 최단 거리인 경우
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    // nxt[i][j] = i -> j 로 갈 때 가장 먼저 방문할 노드이므로 nxt[i][k] 저장
                    dist[i][j] = dist[i][k] + dist[k][j];
                    nxt[i][j] = nxt[i][k];
                }
            }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] == INF)
                cout << "0 ";
            else
                cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (dist[i][j] == 0 || dist[i][j] == INF)
            {
                cout << "0\n";
                continue;
            }

            vector<int> path;
            int st = i;
            while (st != j)
            {
                path.push_back(st);
                st = nxt[st][j];
            }
            path.push_back(j);
            cout << path.size() << ' ';

            for (auto x : path)
                cout << x << ' ';
            cout << '\n';
        }
    }
}