[C/C++] 백준 11780번 - 플로이드 2 (플로이드 와샬)

 

7개월 전에 풀이를 했었는데 재채점 되어 다시 풀어본 문제입니다.

100%에서 틀리시는 분들은 아래의 반례로 해답을 찾으실 수 있을 것 같습니다.

4
4
1 2 1
1 3 1
3 2 1
2 1 1

(갈 수 없는 경로에는 0이 출력돼야 하는 반례)

 

문제

n(1 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

출력

먼저, n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

그 다음에는 n×n개의 줄을 출력해야 한다. i×n+j번째 줄에는 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 k를 출력한다. 그 다음, 도시 i에서 도시 j로 가는 경로를 공백으로 구분해 출력한다. 이때, 도시 i와 도시 j도 출력해야 한다. 만약, i에서 j로 갈 수 없는 경우에는 0을 출력한다.

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 100001

int n, m, u, v, cost;
int map[101][101];
int route[101][101];
vector<int> path;

void pathfind(int start, int end)
{
    int stopover = route[start][end]; // 시작점

    while (stopover != 0)
    {
        path.push_back(stopover);
        stopover = route[start][stopover];
    }
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                map[i][j] = INF;
    
     while (m--)
     {
         cin >> u >> v >> cost;
         map[u][v] = min(map[u][v], cost);
         route[u][v] = u;
     }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (map[i][j] > map[i][k] + map[k][j])
                {
                    map[i][j] = map[i][k] + map[k][j];
                    route[i][j] = route[k][j];
                }

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

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j) cout << 0 << '\n';
            else
            {
                pathfind(i, j);
                if (path.empty() && map[i][j] > 100000) {
                    cout << 0;
                }
                else {
                    cout << path.size() + 1 << " ";
                    for (int i = 0; i < path.size(); i++) // 경유지
                        cout << path[path.size() - i - 1] << " ";
                    cout << j << " "; // 도착점
                }
                cout << '\n';
            }
            path.clear();
        }
    }
}

 

중간에 재채점되어 틀렸습니다 ㅜ

++ 재채점 후 다시 풀이!

 

 

풀이 방법

 

<변수 정의>

map[i][j] : 플로이드 와샬 알고리즘으로 구하는 최소비용을 저장할 배열

route[i][j] : 플로이드 와샬 알고리즘으로 최소 비용이 갱신될 때마다 도시 i에서 도시 j로 갈 때의 경유지를 기록

 

출력은 먼저 플로이드 와샬방법으로 구한 모든 정점에서 모든 정점으로의 최소 비용을 n x n 크기로 출력한다.

그리고 n x n 줄에는 도시 A에서 도시 B로 가는 경로에 포함되어 있는 도시의 개수를 출력 후 그 경로도 출력해야 한다. 

예를 들어 "5 2 4 5 1 3"의 경우는 경로 내의 도시 수가 5개 이고 그 경로는 2-4-5-1-3이라는 의미이다.

 

위의 풀이 코드에서의 핵심은 route[i][j]배열을 만들어 도시 i에서 도시 j로 갈 때의 경유지를 저장하는 것이다.

 

 

예를 들어 아래의 코드로 route배열을 출력해보면 다음과 같다.

for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= n; j++)
		cout << route[i][j] << " ";
	cout << '\n';
}

5행 3열의 값이 1이라는 의미는 도시 5에서 도시 3으로 갈 때 경유하는 도시는 1이라는 의미이다. 

 

이러한 route배열을 이용해서 pathfind함수로 시작점~도착점 전까지의 경로를 스택에 저장한다.

void pathfind(int start, int end)
{
    int stopover = route[start][end]; // 시작점

    while (stopover != 0)
    {
        path.push_back(stopover);
        stopover = route[start][stopover];
    }
}

 

그리고 스택의 특성을 이용하여 top부터 pop하면서 경로를 출력한다.

 

 

 

www.acmicpc.net/problem/11780

11780번: 플로이드 2