[ 백준 11780 ] 플로이드2 (C++)

백준의 플로이드2(11780) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 출력이 굉장히 긴 형태인데, 해당 출력에 맞는 답을 구하기 위해서 문제를 크게 2가지로 나눠보자.

출력을 보게 되면, 크게 2가지로 나눌 수가 있다.

첫 번째는 N x N 칸 만큼 각 도시에서 도시별로 가는데 걸리는 최소비용을 출력하는 것이다.

예를 들어서 N = 3 인 입력이 주어진다면, 이는 도시가 '3개' 존재한다는 의미이고, 가장 첫 번째로 출력해야 하는 것은

1번 도시에서 1번도시, 2번도시, 3번도시로 가는데 걸리는 최소비용 , 2번도시에서 1번도시, 2번도시 3번도시로 가는데 걸리는

최소비용, 3번도시에서 1번도시, 2번도시, 3번도시로 가는데 드는 최소비용을, 즉 총 9개(N x N개) 만큼을 출력해 주어야 한다.

이 부분을 본인은 '플로이드 워샬 알고리즘'을 이용해서 해결하였다.

플로이드 워샬 알고리즘에 대해서 간략하게만 이야기해보자면, 다익스트라 알고리즘 혹은 벨만포드 알고리즘과 마찬가지로

'최소비용을 구할 때 사용하는 알고리즘' 이다. 차이점이라고 하면, 다익스트라 알고리즘과 벨만포드 알고리즘은 '한 정점에서

다른 모든 정점으로의 최소비용' 을 구할 때 일반적으로 사용되는 알고리즘들이고, 플로이드 워샬 알고리즘은 '모든 정점간의

최소비용을 구할 때 사용하는 알고리즘' 이라고 생각하면 된다.

즉 ! 우리는 모든 정점간의 최소비용을 구해서 출력해야 하므로 플로이드 워샬 알고리즘을 이용해서 구할 수 있다.

플로이드 워샬 알고리즘은 보통 O(N^3) 의 시간복잡도 내에서 해결하는 방식으로 구현된다. 일반적으로는 3중 for문을 이용해서

구현하게 된다.

for (int k = 1; k <= N; k++)
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == j) continue;
            if (Cost[i][j] > Cost[i][k] + Cost[k][j])
            {
                Cost[i][j] = Cost[i][k] + Cost[k][j];
            }
        }
    }
}

플로이드 워샬 알고리즘을 구현한 코드이다.

line1)에서 반복되는 'k'는 중간점을, line3) 에서 반복되는 'i'는 시작점을, line5)에서 반복되는 'j'는 도착점을 의미한다.

즉, "i번 정점에서 j번 정점으로 가는데 걸리는 최소비용"을 구하는 과정인데, 그 과정에서 어딘가를 거쳐서 가는것이

더 적은 비용이 든다면, 다시 말해서 k번 정점을 통해서 가는 비용이 i번 정점에서 j번 정점으로 다이렉트로 가는 비용보다

더 적게 든다면, k번 정점을 거쳐 가는 비용으로 계산을 하는 과정이다.

위의 알고리즘을 통해서 첫 번째 출력에 대한 답을 구할 수 있다.

두 번째는, 해당 정점들을 최소비용이 드는 루트로 갔을 때, 거쳐가는 정점들을 출력해야 하는 것이다.

예를 들어서 1번 정점에서 2번정점으로 갈 때, 다이렉트로 가는 방식이 가장 적은 비용이 든다면, '2 1 2' 와 같은 형태로

출력해야 한다. '2 1 2' 에서 앞에 '2'는 거쳐간 정점의 갯수, 뒤에 '1'과 '2'는 해당 정점들을 의미한다.

즉 ! 우리는 거쳐갈 때 더 적은 비용이 드는 경우 때문에 중간 루트를 알고 있어야 할 필요가 있다.

이 부분을 위해서 본인은 2차원 배열을 하나 만들어서 루트를 저장해 주었다.

int Route[a][b] = c 의 의미는 "정점 a에서 정점 b로 최소 비용으로 갈 때, 거쳐가는 정점은 c번 정점입니다" 를 의미한다.

위의 값을 그럼 언제 어떻게 구해야할까 ?? 바로 위에서 구현해놓은 플로이드 워샬 알고리즘을 통해서 최소 비용을 구하는

과정에서 구할 수 있다.

for (int k = 1; k <= N; k++)
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == j) continue;
            if (Cost[i][j] > Cost[i][k] + Cost[k][j])
            {
                Cost[i][j] = Cost[i][k] + Cost[k][j];
                Route[i][j] = k;
            }
        }
    }
}

바로 이렇게 설정해 준다면, "i번 정점에서 j번 정점으로 갈 때, 거쳐가야 하는 정점은 k번 정점입니다"를 의미하게 된다.

이 후 경로를 찾는 과정에 대해서 간단한 예시를 통해서 알아보자.

예를 들어서 A번 정점에서 B번정점으로 갈 때, C번 정점을 거쳐서 가는 것이 가장 최소비용인 경우를 생각해보자.

그렇다면 우리는 현재 Route[A][B] = C 라는 것을 알고 있을 것이다.

그럼 우리는 이 경로를 다음과 같이 2개의 경로로 나눠볼 수가 있다. A → C , C → B !

이 과정을 본인은 재귀를 통해서 구현하였다. 재귀의 매개변수로 (시작점, 도착점)을 호출해 주었다.

거쳐가는 정점이 없다면 상관이 없겠지만, 위에서 봤듯이 거쳐가는 정점이 있다면, (시작점, 도착점)을

(시작점 , 중간점) , (중간점 , 도착점)으로 나눠서 재귀를 호출해 주었다.

이 재귀의 기저조건은 "Route[시작점][도착점] = 0" 일 때로 설정해 주었다. 왜냐하면 더 이상 거쳐갈 정점이 없다면,

해당 루트를 (시작점, 중간점), (중간점, 도착점) 으로 나눌 수가 없기 때문이다.

이 경로를 저장하기 위해서 vector를 하나 선언해서 사용해 주었다. 기저 조건에 만족한다면, 매개변수로 호출되어 있는

시작점과 도착점을 vector에 순차적으로 삽입해 주었다.

void Find_Route(int Start, int End)
{
    if (Route[Start][End] == 0)
    {
        V.push_back(Start);
        V.push_back(End);
        return;
    }
    Find_Route(Start, Route[Start][End]);
    V.pop_back();
    Find_Route(Route[Start][End], End);
}

위와 같은 형태로 구현하였다. line3)이 재귀의 종료조건을 의미한다.

line 9 ~ 11을 보게되면 거쳐가는 정점이 있을 경우, 해당 경로를 2가지 경로로 나눠서 탐색하는 과정이다.

line 10에서 Vector의 값을 하나 삭제하는 연산이 있는데, 이는 이러한 현상을 막기 위해서이다.

위의 예시에서 A → B로 갈 때 최단경로는 A → C , C → B 라고 했는데, line 10)이 없다면 아마 경로가 "A C C B" 로 출력될

것이다. 우리가 원하는 경로는 "A C B" 이기 때문에, 중복된 출력을 방지하기 위해서 값을 하나 삭제해 준 것이다.

즉, 시작점 → 중간점 , 중간점 → 도착점 으로 탐색을 하게 되면, "중간점"이 2번 들어가게 되므로 원하는 출력 형태대로

출력을 할 수가 없다. 따라서 한 번 삭제해주는 연산이 필요하다 !

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 110
#define INF 1e9
using namespace std;
 
int N, M;
int Cost[MAX][MAX];
int Route[MAX][MAX];
vector<int> V;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            Cost[i][j] = INF;
        }
    }
 
    for (int i = 0; i < M; i++)
    {
        int a, b, c; 
        cin >> a >> b >> c;
        Cost[a][b] = Min(Cost[a][b], c);
    }
}
 
void Floyd_Warshall()
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (i == j) continue;
                if (Cost[i][j] > Cost[i][k] + Cost[k][j])
                {
                    Cost[i][j] = Cost[i][k] + Cost[k][j];
                    Route[i][j] = k;
                }
            }
        }
    }
}
 
void Find_Route(int Start, int End)
{
    if (Route[Start][End] == 0)
    {
        V.push_back(Start);
        V.push_back(End);
        return;
    }
    Find_Route(Start, Route[Start][End]);
    V.pop_back();
    Find_Route(Route[Start][End], End);
}
 
void Solution()
{
    Floyd_Warshall();
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (Cost[i][j] == INF) cout << 0 << " ";
            else cout << Cost[i][j] << " ";
        }
        cout << endl;
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (Cost[i][j] == INF) cout << 0;
            else
            {
                V.clear();
                Find_Route(i, j);
                cout << V.size() << " ";
                for (int k = 0; k < V.size(); k++) cout << V[k] << " ";
            }
            cout << endl;
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}