문제 출처

1. 문제설명

  • N개의 정점과 M개의 간선으로 이뤄진 그래프가 있다.

  • 어떤 정점에서 다른 정점으로 이동하기 위해 가장 먼저 거쳐야 하는 정점을 기록한 경로표를 출력하라

  • 문제 분류
    • Graph, Floyd


2. 알고리즘 설계

  • 플로이드-워셜 경로 복원 문제이다.
  • 문제의 그래프를 보면 무방향 그래프이다.
    • 어떤 두 정점 간 간선이 1개이므로, 중복 처리는 안해도 된다.
    • next[u][v], next[v][u]를 각각 v, u로 처리해야 한다.
  • 플로이드 값을 갱신할 때마다 next 배열의 값을 갱신한다.
  • 출력 관련
    • 기존 코드에서는 cout << (i==j ? '-' : next[i][j])로 했었다.
    • 근데 실제로 출력해보면 ‘-‘에 대한 아스키 코드 숫자가 출력된다.
    • 그래서 아래 코드와 같이 if-else로 두 줄의 출력을 만들어줘야 한다.


3. 전체 코드

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

const int INF = 0x3f3f3f3f, SZ = 202;
int n, m, D[SZ][SZ], nxt[SZ][SZ];

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

	cin >> n >> m;

	for(int i=1; i<=n; i++) {
		fill(D[i]+1, D[i]+n+1, INF);
		D[i][i] = 0;
	}

	for(int u, v, c; m--;) {
		cin >> u >> v >> c;
		D[u][v] = D[v][u] = c;
		nxt[u][v] = v;
		nxt[v][u] = u;
	}

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

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

	return 0;
}