문제
n개의 도시와 m개의 버스 노선이 주어질 때, 모든 도시 쌍 (i, j)에 대해 i에서 j로 가는 최솟값을 구하는 문제이다. 같은 출발지와 목적지를 가진 노선이 여러 개 존재할 수 있으며, 경로가 없으면 0을 출력한다.
입력
- 첫 번째 줄: 도시 수 n (2 이상 100 이하)
- 두 번째 줄: 버스 수 m (1 이상 100,000 이하)
- 이후 m줄: 출발 도시, 도착 도시, 비용
출력
n x n 행렬 형태로 최단 경로 비용을 출력한다. 경로가 없으면 0을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 14 1 2 2 1 3 3 ... | 0 2 3 1 4 12 0 15 2 5 ... |
풀이
플로이드-워셜 알고리즘으로 모든 쌍 최단 경로를 구한다. 중간 노드 k를 거쳐 i에서 j로 가는 경로가 직접 가는 것보다 짧은지 반복 갱신한다.
dist[i][j]를 INF로 초기화하고dist[i][i] = 0으로 설정한다.- 간선 정보를 입력받을 때 같은 구간에 여러 노선이 있으므로
Math.min으로 최솟값만 저장한다. - 3중 for문으로 중간 노드 k(1~n), 출발 i, 도착 j를 순회하며
dist[i][k] + dist[k][j] < dist[i][j]이면 갱신한다. - 출력 시
dist[i][j] >= INF이면 0을, 아니면 값을 출력한다.
핵심 아이디어: Integer.MAX_VALUE를 INF로 사용하면 두 값의 합산 시 오버플로우가 발생하므로 (int) 1e9와 같이 충분히 크지만 안전한 값을 사용해야 한다. 같은 간선이 중복으로 주어질 수 있어 초기 입력 시 최솟값으로 필터링하는 것이 중요하다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day52BOJ11404플로이드 { // 11404 하다 말았음.
static final int INF = (int) 1e9; // 플로이드 함수를 위한 큰 값, MAX_VALUE 안됨
static int N, M;
static int[][] dist;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
dist = new int[N + 1][N + 1];
sb = new StringBuilder();
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (i == j)
continue;
dist[i][j] = INF;
}
}
for (int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int stt = Integer.parseInt(st.nextToken());
int ed = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
dist[stt][ed] = Math.min(dist[stt][ed], cost);
}
floyd();
System.out.println(sb);
br.close();
}
private static void floyd() {
for (int k = 1; k < N + 1; k++) {
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
}
}
}
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
if (dist[i][j] >= INF)
sb.append("0 ");
else
sb.append(dist[i][j] + " ");
}
sb.append("\n");
}
}
}복잡도
- 시간: O(V³) — 3중 for문으로 모든 중간 노드 k를 거치는 경로 갱신
- 공간: O(V²) — n x n 거리 행렬