문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.
  • 모든 정점의 쌍(A, B)에 대해 A에서 B로 가는 비용의 최소값을 구하라.

  • 추가로, 어떤 정점 i에서 j로 가는 경로를 출력하라

  • 문제 분류
    • Graph, Floyd


2. 알고리즘 설계

  • 플로이드-워셜 알고리즘의 경로 복원 문제이다.
    • 생각보다 극악의 난이도였다…
  • 우선, 문제의 첫번째 출력은 플로이드-워셜 값을 출력해주면 된다.
  • 경로 복원
    • 초기화는 간선 a->b에 대해 다음 위치는 b로 저장한다.
    • 이후, 플로이드-워셜 값이 갱신될 때(i->j보다 i->k->j가 더 비용이 적을 때) i->j로 갈 때의 다음 위치인 next[i][j]를 next[i][k]의 값으로 저장한다.
    • 출력은 어떻게 하면 될까?
      • i->j 경로이므로, i를 출력한다.
      • 이후에는 next 배열의 값을 쭉 따라가면 된다.
        • 첫 갱신은 next[cur][j]가 된다.
          • 즉, 현재 위치에서 j로 가는데, 어떤 노드로 이동하는가?
        • 두번째 갱신은 풀어보면 next[next[cur][j]][j]가 된다.
          • 즉, 이전에 이동한 위치에서 j로 가는 경로를 출력하게 된다.
        • 이런식으로 이동을 하다가, 다음 위치가 j랑 같아지면 만나게 된 것이다.
      • cur == j가 탈출 조건이므로, 마지막에 j를 경로에 추가시키면 된다.
  • i==j 즉, 자신에게 가는 경로 또는 i->j로 가는 길이 없는 경우는 경로가 없다


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int a, b, c, n, m;
int arr[102][102], nxt[102][102];

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++)
			arr[i][j] = (i==j ? 0 : INF);

	while(m--) {
		cin >> a >> b >> c;
		arr[a][b] = min(arr[a][b], c);
		nxt[a][b] = b;
	}

	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];
				}
			}

	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++)
			cout << (arr[i][j] == INF ? 0 : arr[i][j]) << ' ';
		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\n";
				continue;
			}

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

			cout << path.size() << ' ';
			for(int x : path) cout << x << ' ';
			cout << '\n';
		}
	}

	return 0;
}