문제
N개의 집하장과 M개의 경로가 있다. 모든 집하장 쌍에 대해, 최단 경로로 이동할 때 첫 번째로 거치는 집하장 번호를 구하라.
입력
첫째 줄에 N, M이 주어지고, 이후 M개의 양방향 경로 (출발, 도착, 비용)가 주어진다.
출력
N×N 경로표를 출력한다. 자기 자신은 "-"로 표시한다.
예제
| 입력 | 출력 |
|---|---|
6 10 1 2 2 1 3 1 2 4 5 2 5 3 2 6 7 3 4 4 3 5 6 3 6 7 4 6 4 5 6 2 | - 2 3 3 2 2 1 - 1 4 5 5 1 1 - 4 1 1 3 2 3 - 6 6 2 2 2 6 - 6 5 5 5 4 5 - |
풀이
플로이드-워셜 알고리즘으로 모든 쌍 최단 경로를 구하면서 경유 경로를 추적한다.
- 거리 행렬 map과 경로 추적 행렬 p를 초기화한다
- 직접 연결된 간선 (u, v)에 대해
p[u][v] = v,p[v][u] = u로 설정한다 - 플로이드-워셜로
map[i][j] > map[i][k] + map[k][j]이면 거리를 갱신하고p[i][j] = p[i][k]로 경로를 갱신한다 p[i][j]가 i에서 j로 가는 최단 경로의 첫 번째 경유지가 된다
핵심 아이디어: 플로이드-워셜에서 거리를 갱신할 때 p[i][j] = p[i][k]로 설정하면, i에서 j까지의 최단 경로에서 i 다음에 방문하는 노드를 추적할 수 있다.
코드
package day399;
import java.io.*;
import java.util.*;
public class Day376BOJ1719택배 { //
static int N, M;
static Integer[][] map, p;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new Integer[N + 1][N + 1];
p = new Integer[N + 1][N + 1];
for (int i = 1; i < N + 1; i++)
Arrays.fill(map[i], 1 << 20);
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[u][v] = map[v][u] = Math.min(map[u][v], c);
p[u][v] = v;
p[v][u] = u;
}
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 (map[i][j] > map[i][k] + map[k][j]) {
map[i][j] = map[i][k] + map[k][j];
p[i][j] = p[i][k];
}
}
}
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (i == j)
sb.append("- ");
else
sb.append(p[i][j] + " ");
}
sb.append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N³) - 플로이드-워셜
- 공간: O(N²) - 거리 행렬 및 경로 행렬