문제
모든 정점을 거치는 최단경로를 찾는(왕복 운동 포함) 플로이드 워셜 알고리즘의 기본문제. N개의 도시가 있고 A -> B 도시를 이동하는 간선이 M개 존재, 사이에 버스를 타는 비용이 존재한다.
해결방향성
이 문제는 방향 그래프 문제이다. 처음에 무방향 그래프로 풀었다가 최단경로가 더 줄어서 애먹었다. 우선 플로이드 - 워셜 알고리즘에 대해 설명해 보겠다.
플로이드 워셜 알고리즘은 3단계를 거친다.
1. 초기화 : 처음 초기화는 보통 자기자신으로의 경로는 0으로, 나머지는 INF로 초기화한다. INF는 보통 정점 X 가중치이다. (때에따라 다르게 설정해 주면된다.)
2. 주어진 간선을 바탕으로 최단경로 결정
: 말그대로 그래프를 연결할때 받았던 가중치대로, 가장 최소가중치를 dist[][] 이차원배열에 넣어주면된다. Math.min 정적메소드를 사용하면된다.
3. 1->V 정점을 모두 거치는 경로중 최단경로를 결정.
이 3가지 과정만 거치면되는 간단한 알고리즘이라, 되게 날먹이 가능한게 많다. 하지만 100개의 정점만있어도 100100100 = 1_000_000 계산이 100만번이 넘어가니 쓸때 주의가 필요하다.
: 이것도 마찬가지로 i->j를 가는 경로와 i->k->j로 가는 경로중 최소값을 dist[][] 배열에 넣어주면된다.
코드
import java.io.*;
import java.util.*;
class Vertex{
int num;
int cost;
public Vertex(int num, int cost) {
this.num = num;
this.cost = cost;
}
}
public class Main {
private static ArrayList<ArrayList<Vertex>> graph;
private static int N;
private static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
graph = new ArrayList<>();
graph.add(new ArrayList<>());
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 1; i <= M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.get(start).add(new Vertex(end, cost));
//graph.get(end).add(new Vertex(start, cost));
}
// 그래프 연결끝, 정점, 간선 모두 입력받음.
dist = new int[N + 1][N + 1]; // 1 ~ N까지 최단경로를 저장
floydWarshall();
// 최단경로 dist[][] 배열 출력
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dist[i][j] == INF) {
dist[i][j] = 0;
}
bw.write(String.valueOf(dist[i][j]) + " ");
}
bw.write("\n");
}
bw.flush();
br.close();
bw.close();
}
static int[][] dist;
static int INF = 100_000_000; // n : 100 * cost : 100_000 _는 자릿수 구별
private static void floydWarshall() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) {
dist[i][j] = 0; // 자기 자신으로의 경로는 최단경로가 없음. 0.
continue;
}
dist[i][j] = INF; // 최단경로 배열 초기화
}
}
// 먼가 이상함. 일단 후보 1이 여기. 최단경로가 더해지지않은 느낌.
// 해결법 : 입력받은 간선들의 최단경로를 미리 입력해둠.
// i -> j 경로중 최단경로를 dist에 미리 저장
// 현재 고민: arraylist는 가독성이 딸림... 약간의 생각을 거쳐야함. 어떻게 해결할까?
for (int i = 1; i <= N; i++) {
for (Vertex endVertex: graph.get(i)) { // 끝점까지의 거리중 최단경로를 dist 배열에 대입
dist[i][endVertex.num] = Math.min(dist[i][endVertex.num], endVertex.cost); // 현재 dist[i][j]와 cost를 비교해서 작은걸 대입?
//dist[endVertex.num][i] = Math.min(dist[endVertex.num][i], endVertex.cost);
}
}
for (int k = 1; k <= N; k++) { // 1~N까지 모든 정점을 거쳐가는건에 대하여
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) { // i -> j까지 가는 경로중 최단경로 선택
// i -> j 와 i -> k -> j 중 최단경로를 대입. 그렇기 위해선 i -> j사이의 경로가 계산 되어야함 미리.
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// 계산 끝.
}
}
결론
참고블로그: https://sskl660.tistory.com/61
여기 플로이드 워셜을 이해하는데 아주 도움이 되는 블로그이다. 플로이드 워셜의 핵심은 1~N까지 모든 정점을 거치는 경로 중에서, 1~N -> 1~N까지 최솟값중에 거치는 경로와 비교해서 최소를 또 찾는 문제라, 그 과정을 잘 보여주고 있다. O(V^3)의 시간복잡도를 가진다.
