https://www.acmicpc.net/problem/11404
문제 요약
N개의 도시와 M개의 버스가 존재한다고 하자. 이때 각 버스는 한 번 사용할 때의 비용이 있다.
모든 도시 쌍 (A, B)에 대해 도시 A에서 B로 가는데 필요한 최소 비용을 구하여라.
만약 도달하지 못하는 경우에는 0으로 출력한다.
도시의 개수 N은 최대 100이다.
버스의 개수 M은 최대 10만이다.
버스의 정보는 시작 도시, 도착 도시, 비용 순으로 주어진다.
이때 비용은 10만 이하의 자연수로 주어진다.
버스의 시작 도시와 도착 도시가 같은 경우는 없다.
단, 시작 도시와 도착 도시를 연결하는 버스는 하나가 아닐 수 있다.
문제 접근
도시를 노드, 버스를 엣지로 치환하면 이 문제는 그래프에서 노드 간의 최단 거리를 구하는 문제로 생각할 수 있다.
고민점 1: 어떤 알고리즘을 사용해야 할까?
그래프에서 최단 거리를 구할 때 사용할 수 있는 대표적인 3가지 알고리즘으로는 다익스트라, 벨만 포드, 플로이드 워셜이 있다.
다익스트라 알고리즘은 하나의 정점에서 다른 정점들 간의 최단 거리를 구하는 알고리즘이다. 우선순위 큐를 이용해 구현하면 시간복잡도는 O(ElogV)로 얻어진다. (V는 정점의 개수, E는 간선의 개수)
벨만 포드 알고리즘도 하나의 정점에서 다른 정점든 간의 최단 거리를 구하는 알고리즘이다. 다만 다익스트라 알고리즘과 다른 점은 간선의 가중치가 음수일 때에도 사용할 수 있다는 점이다. 시간복잡도는 O(VE)이다.
플로이드 워셜 알고리즘은 그래프를 구성하는 모든 정점 간의 최단 거리를 구하는 알고리즘이다. 시간복잡도는 O(V^3)이다.
위의 내용을 고려하면 문제 상황 상 플로이드 워셜 알고리즘을 이용하여 문제를 해결하는 것이 적절한 것 같다.
애초에 문제 이름이 플로이드이기도 하다.
그렇다고 다른 알고리즘을 사용하면 안되는 것은 아니다.
먼저 이 문제에서 다익스트라 알고리즘도 사용할 수 있다. 간선의 비용이 음수가 아닌 자연수로 주어지며, 각 정점에 대해서 다익스트라 알고리즘을 수행하는 시간복잡도 O(VElogV)을 고려하면 최대 100*100000*log(100)이기 때문에 시간 안에 수행할 수 있다. 다만 플로이드 워셜에 비해 상대적으로 많이 느릴 것이다.
하지만 벨만 포드 알고리즘은 사용할 수 없다. 각 정점에 대해 벨만 포드 알고리즘을 수행하는 시간복잡도 O(V^2E)는 최대 100*100*100000이 되기 때문에 시간 내에 수행할 수 없다.
어쨌든 문제 의도에 맞게 플로이드 워셜 알고리즘을 사용하자!
고민점 2: 플로이드 워셜 알고리즘을 어떻게 구현하지?
플로이드 워셜 알고리즘은 정점 간의 최단 거리를 기록한 배열을 기반으로 시작 정점, 도착 정점, 그리고 경유 정점이라는 세 가지 정점을 사용한다.
최단 거리 기록 배열 dist에서 시작 정점 A와 도착 정점 B 간의 최단 거리를 dist[A][B]라고 해보자.
그러면 경유 정점 K에 대해 dist[A][B] = Math.min(dist[A][B], dist[A][K] + dist[K][B])라는 공식으로 최단 거리를 갱신하며 기록하는 것이다.
이는 결국 삼중 반복문으로 구현할 수 있어 상당히 간단한데, 중요한 점은 경유 정점을 훑는 반복문이 가장 바깥에 존재해야 한다는 것이다.
왜냐하면 결국 우리는 시작 정점에서 도착 정점까지의 최단 거리를 구하는 것이 목적이기 때문에 가능한 모든 경우를 고려해야 하기 때문이다.
만약 시작점이나 도착점을 가장 바깥쪽에서 훑는다면, 해당 시작점이나 도착점의 값은 이미 결정되었기 때문에 추후에 다시 갱신되지 않게 된다. 이는 모든 경우를 고려하지 못함을 의미한다.
풀이
기본적인 아이디어는 다음과 같다.
- 입력을 받아 인접 배열 형태의 그래프를 구성한다. 이때 같은 구간의 간선이 여러 번 주어지면, 가장 비용이 작은 것을 기록한다.
- 삼중 반복문으로 플로이드 워셜 알고리즘을 수행한다. 이때 거리가 0일 때는 경로가 존재하지 않으므로 넘어가고, 시작점과 도착점이 같은 경우도 넘어간다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static int[][] shortestPath;
public static void getInput() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
shortestPath = new int[n+1][n+1];
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < n+1; j++) {
shortestPath[i][j] = 0;
}
}
for (int i = 0; i < m; i++) {
StringTokenizer stm = new StringTokenizer(br.readLine());
int a = Integer.parseInt(stm.nextToken());
int b = Integer.parseInt(stm.nextToken());
int c = Integer.parseInt(stm.nextToken());
if (shortestPath[a][b] == 0) shortestPath[a][b] = c;
else shortestPath[a][b] = Math.min(shortestPath[a][b], c);
}
}
public static void findShortestPath() {
for (int z = 1; z < n+1; z++) {
for (int y = 1; y < n+1; y++) {
if (shortestPath[y][z] == 0) continue;
for (int x = 1; x < n+1; x++) {
if (shortestPath[z][x] == 0 || y == x) continue;
if (shortestPath[y][x] == 0) {
shortestPath[y][x] = shortestPath[y][z] + shortestPath[z][x];
}
else {
shortestPath[y][x] = Math.min(shortestPath[y][x], shortestPath[y][z] + shortestPath[z][x]);
}
}
}
}
}
public static void printAnswer() {
StringBuilder sb = new StringBuilder();
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < n+1; j++) {
sb.append(shortestPath[i][j]+" ");
}
sb.append("\n");
}
System.out.println(sb);
}
public static void main(String[] args) throws IOException {
getInput();
findShortestPath();
printAnswer();
}
}회고
몇 달 전에 풀었던 문제라서 코드 작성 스타일이 현재와 상당히 다르고, 주석이 작성되어 있지 않아서 코드 이해가 쉽지는 않았다.... 주석을 꼭 작성하자.
당시에는 main에 코드를 모두 작성하지 않고 역할에 따라 함수를 새로 작성하고자 했는데, 목표는 괜찮았지만 지금 보면 각 함수가 꼭 하나의 역할만 하고 있지는 않다. 개선이 필요해보인다.
왜 정점 간의 최단 거리 배열을 INTEGER.MAX_VALUE나 -1으로 초기화하지 않고 0으로 초기화했는지 의문이었는데, 문제에서 도달하지 못하는 경우에 0을 출력하도록 했기 때문이었다.
