문제
N개의 도시와 M개의 버스 노선이 주어진다. 모든 도시 쌍 (i, j)에 대해 i에서 j로 가는 최소 비용을 구하고, 그 경로상의 도시 목록도 함께 출력해야 한다. 기본 플로이드–워셜(BOJ 11404)에서 경로 역추적이 추가된 문제이다.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에 M이 주어진다. (1 ≤ M ≤ 100,000) 이후 M개의 줄에 출발 도시, 도착 도시, 비용이 주어진다.
출력
N개의 줄에 최소 비용 행렬을 출력한다. 경로가 없으면 0을 출력한다.
이후 N^2개의 줄에 경로 정보를 출력한다. 경로가 없거나 자기 자신이면 0을 출력하고, 경로가 있으면 경유 도시 수+1과 경로 도시 목록을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 14 (간선 14개) | 5x5 비용 행렬, 이후 25개의 경로 출력 |
풀이
플로이드–워셜 알고리즘으로 모든 쌍 최단 경로를 계산하면서 route[i][j] 배열에 중간 경유 정보를 기록하여 경로를 역추적한다.
cost[i][j]를 INF로 초기화하고, 입력된 간선으로 최솟값을 갱신한다.route[x][y] = x로 초기화(직접 간선 경유지 = 출발지)한다.- 플로이드–워셜 3중 반복문
(k, i, j):cost[i][j] > cost[i][k] + cost[k][j]이면cost[i][j]를 갱신하고route[i][j] = route[k][j]로 기록한다. - 비용 행렬 출력:
cost[i][j] < 100000이면 실제 비용, 그 이상이면 0을 출력한다. - 경로 역추적:
route[start][end]에서 시작하여route[start][idx]를 따라가며 스택에 쌓고, 출발지까지 역추적 후 스택을 뒤집어 출력한다.
핵심 아이디어: route[i][j]는 "i에서 j로 가는 최단 경로에서 j 직전에 방문하는 도시"를 기록한다. 경로 갱신 시 route[i][j] = route[k][j]로 설정하면, k를 경유하는 경로에서 j 직전 도시가 자동으로 반영된다. 스택을 활용하면 역추적을 순방향 경로로 변환할 수 있다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
public class Day64BOJ11780플로이드마샬이뭔데 { // 11780 플로이드 2
static final int INF = 1000001;
static StringBuilder sb;
static int N, M;
static int[][] cost, route;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
cost = new int[N + 1][N + 1];
route = new int[N + 1][N + 1];
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (i != j)
cost[i][j] = 1000001;
}
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
cost[x][y] = Math.min(cost[x][y], Integer.parseInt(st.nextToken()));
route[x][y] = x;
}
for (int k = 1; k < N + 1; k++) { // 구선생님..
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (cost[i][j] > cost[i][k] + cost[k][j]) {
cost[i][j] = cost[i][k] + cost[k][j];
route[i][j] = route[k][j];
}
}
}
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (cost[i][j] < 100000) {
sb.append(cost[i][j] + " ");
} else {
sb.append("0 ");
}
}
sb.append("\n");
}
for (int i = 1; i < N + 1; i++) {
path(i, N);
}
System.out.println(sb);
br.close();
}
public static void path(int start, int n) { // 구선생님..
Stack<Integer> st;
for (int end = 1; end < n + 1; end++) {
if (start == end)
sb.append("0" + "\n");
else {
st = new Stack<>();
int idx = route[start][end];
while (idx != 0) {
st.push(idx);
idx = route[start][idx];
}
if (st.isEmpty()) { // start에서 end로 갈 수 없는 경우
sb.append("0" + "\n");
} else { // 경로 출력
sb.append((st.size() + 1) + " ");
while (!st.isEmpty()) {
sb.append(st.peek() + " ");
st.pop();
}
sb.append(end + "\n");
}
}
}
}
}복잡도
- 시간: O(V^3) — 플로이드–워셜 3중 반복문
- 공간: O(V^2) — 비용 행렬 및 경로 행렬