[Algorithm] Baekjoon 11780번 : 플로이드 2

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
int n, m;
int graph[103][103] = { 0 };
int middlePathCity[103][103] = { 0 };
const int maxNum = 0x3f3f3f3f;
 
 
vector<int> route;
 
void FindPath(int start, int end)
{
    if (middlePathCity[start][end] == 0) // 중간도시 더 이상 없으면
    {
        route.push_back(start);
        route.push_back(end);
        return;
    }
 
    FindPath(start, middlePathCity[start][end]);
    route.pop_back(); // middlePathCity[start][end]가 겹쳐서 하나 빼줘야ㅗ딤.
    FindPath(middlePathCity[start][end], end);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    memset(graph, 0x3f, sizeof(graph));
 
    for (int i = 1; i <= n; ++i)
    {
        graph[i][i] = 0;
    }
 
    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        graph[a][b] = min(graph[a][b], c);
    }
 
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (graph[i][k] == maxNum) continue;
            
            for (int j = 1; j <= n; ++j)
            {
                if (graph[i][k] + graph[k][j] < graph[i][j])
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
                    middlePathCity[i][j] = k; // i와 j 사이에 k도시가 있다는 뜻.
                }
            }
            
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (graph[i][j] == maxNum)
            {
                printf("%d ", 0);
            }
            else
            {
                printf("%d ", graph[i][j]);
            }
        }
 
        printf("\n");
    }
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == j || graph[i][j] == maxNum)
            {
                printf("%d\n", 0);
            }
            else
            {
                route.clear();
                FindPath(i, j);
                printf("%d ", route.size());
 
                for (int k = 0; k < route.size(); ++k)
                {
                    printf("%d ", route[k]);
                }
                printf("\n");
            }
        }
    }
}
 
 

 

 

단순히 최단거리 뿐만 아니라 경로까지 구해야 하는 문제이다.

경로를 구해야하기 때문에 테이블에 업데이트할 때마다 (graph[i][k] + graph[k][j] < graph[i][j]) , 

i와 j도시 사이에 k도시가 있다는걸 기록한다.

형태는 middleRouteCity[i][j] = k;  가 될 것이다.

 

헷갈리지 말아야 할 것은 i도시와 j도시의 여러 도시 가운데 하나로 k가 있다는 것일 뿐이다. 

i도시 바로 옆에있는지, j도시 바로옆에있는지 어딨는지는 모른다. 그저 경로상에 확실히 존재한다는 것 뿐이다.

최단거리값들은 그냥 출력해주면 되고, 경로를 구하기위해서는 재귀함수를 통해 구해줬다.

어차피 중간경로가 어떤값이든, 그걸 기준으로 앞뒤로 나눠가면서 재귀호출하기 때문에 정답을 구할 수 있다.

 

재귀호출할 때는 두 구간으로 나누는과정에서 middleRouteCity[start][end]값이 겹치니 한번 pop_back해줘야 한다.

(위 재귀호출코드 기준으로)