플로이드 알고리즘: 모든 쌍의 최단 경로를 구하는 알고리즘
c.f. 벨만 포드/다익스트라 알고리즘: 시작점이 1개일 때
이 문제는 플로이드 알고리즘을 써서 풀 수 있다.
그런데, 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 K를 출력해야 하기때문에
그동안 지나왔던 경로도 저장해야 한다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int mat[][] = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(mat[i], 1000000);
mat[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int start = in.nextInt();
int end = in.nextInt();
int cost = in.nextInt();
mat[start][end] = Math.min(mat[start][end], cost);
}
int route[][] = new int[n + 1][n + 1];
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (mat[i][j] > mat[i][k] + mat[k][j]) {
route[i][j] = k; // i~j를 갈 때 k를 거친다
mat[i][j] = mat[i][k] + mat[k][j];
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
System.out.print(mat[i][j] + " ");
}
System.out.println();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
System.out.println("0");
} else {
LinkedList<Integer> list = new LinkedList<Integer>();
routeList(i, j, route, list);
System.out.print(list.size() + " ");
for (int k = 0; k < list.size(); k++) {
System.out.print(list.get(k) + " ");
}
System.out.println();
}
}
}
}
public static void routeList(int start, int end, int route[][], LinkedList<Integer> list) {
if (route[start][end] == 0) { // i~j를 갈 때 거치는 점이 없을
list.add(start);
if (start != end) {
list.add(end);
}
} else {
int middle = route[start][end]; // i~j를 갈 때 경유
routeList(start, middle, route, list);
list.removeLast(); // 중복 제거
routeList(middle, end, route, list);
}
}
}그동안 지나왔던 경로를 저장할 때에는 route[i][j]에 i와 j를 지날 때 경유한 점을 저장하도록 한다.
즉, route[i][j]에는 i->j 간선이 원래 어디를 가르켰는지 저장한다.
경유했던 점들의 리스트를 가져올 때에는 routeList에서 list에 하나씩 넣는데
routeList(start, middle, route, list)와 routeList(middle, end, route, list)에서 middle 부분이 list에 두번 중복되어 들어가므로 한 번 제거해줘야한다.
'알고리즘 공부 > boj' 카테고리의 다른 글
| boj 1956: 운동 (0) | 2020.07.10 |
|---|---|
| boj 1507: 궁금한 민호 (0) | 2020.07.10 |
| boj 1806: 부분합 (0) | 2020.07.09 |
| boj 1753: 최단경로 (0) | 2020.07.08 |
| boj 1504: 특정한 최단 경로 (0) | 2020.07.08 |
