문제
[문제]
n(2 ≤ n ≤ 100)개의 도시가 있다.
그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다.
각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다.
그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다.
먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다.
버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다.
시작 도시와 도착 도시가 같은 경우는 없다.
비용은 100,000보다 작거나 같은 자연수이다.
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
[출력]
n개의 줄을 출력해야 한다.
i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다.
만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.
아이디어
Floyd-Warshall Algorithm
-
모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘의 경우 한 지점에서 다른 모든 지점들간의 최단 경로를 구하는 알고리즘이다.
-
모든 지점에서 다른 지점까지 이동할 때, 지나게되는 중간 지점을 기준으로 최단경로를 탐색한다.
-
다익스트라 알고리즘과 달리, 음의 간선이 포함된 경우에도 최단거리를 구할 수 있다.
-
Dynamic Programming의 일종이다.
- A에서 B까지 가는 경로, Mid 지점을 거친다고 할 때
dp[A][B] = min(dp[A][B], dp[A][Mid] + dp[Mid][B])
-
시간복잡도는 O(N^3)
- 문제에서 n = 100이므로, 시간 안에 풀 수 있다.
제출 코드
Python
import sys
input = sys.stdin.readline
INF = float('inf')
n = int(input())
dist = [[INF] * (n+1) for _ in range(n+1)]
m = int(input())
for _ in range(m):
a, b, c = map(int, input().split())
dist[a][b] = min(dist[a][b], c) # 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음
# 자기 자신의 비용 0으로 설정
for i in range(1, n+1):
dist[i][i] = 0
# Floyd Warshall - 중간 지점을 기준으로!
for mid in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
dist[i][j]= min(dist[i][j], dist[i][mid] + dist[mid][j])
for i in range(1, n+1):
for j in range(1, n+1):
if dist[i][j] == INF:
print(0, end=' ')
else:
print(dist[i][j], end=' ')
print()Java
package BOJ;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_플로이드_11404 {
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException, NumberFormatException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] dist = new int[n+1][n+1];
// dist 값 초기화
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < n+1; j++) {
if (i == j) {
dist[i][j] = 0;
}
else {
dist[i][j] = INF;
}
}
}
for (int i = 0; i < m; i ++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
dist[a][b] = Integer.min(dist[a][b], c);
}
// Floyd-Warshall
for (int mid = 0; mid < n+1; mid++) {
for (int a = 0; a < n+1; a++) {
for (int b = 0; b < n+1; b++) {
if (dist[a][mid] == INF || dist[mid][b] == INF) {
continue;
}
dist[a][b] = Integer.min(dist[a][b], dist[a][mid] + dist[mid][b]);
}
}
}
// 출력
StringBuilder sb = new StringBuilder();
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");
}
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}
참고 사이트
코뉴로그