[BOJ 백준] 플로이드(11404) Java

링크 : https://www.acmicpc.net/problem/11404

문제 설명 :

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을 출력한다.

예제 입력 :

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

예제 출력 :

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

접근법 :
1) 어떻게 풀 것인가?

모든 도시 쌍의 (A, B)의 최단경로를 구해야하며, n이 100으로 비교적 작다.

플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하면, 모든 정점간의 최소 거리를 구할 수 있으며,
이때 시간복잡도는 O (N^3)이다.

따라서, n이 300~500이하로 비교적 작을때만 이용 가능하다.

플로이드 워셜 알고리즘을 요약하면
N^3의 3중 for문을 돌면서
현재 갖고 있는 (출발지 - 도착지)의 최단경로 값이 빠른지,
(출발지 - 경유지) + (경유지 - 도착지)의 최단경로 값이 빠른지 비교하는 알고리즘이다.

// 3. 플로이드-워셜 진행
		// 3중 for문 순서 경유 - 출발 - 도착
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					// 기존 (출발-도착) > (출발-경유) + (경유-도착) 이면 갱신
					if (dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}

참고할만한 플로이드-워셜 문제 백준 2458 키 순서
문제 : https://www.acmicpc.net/problem/2458
풀이 : https://subbak2.tistory.com/52

2) 시간복잡도
N이 100이므로 N^3 = 1,000,000으로 양호하다

추가로 시간을 정답 출력시 println, 또는 BufferedWriter의 write를
100^2 번 출력하면 최대 1만 번 함수를 호출하므로 가능하면 StringBuilder로 모아서 출력하는게 좋아보인다.
(Java 기준 - 488ms)

3) 공간복잡도
n이 100으로 매우 작아 고려하지 않음.

4) 풀면서 놓쳤던점
특별히 없음.

5) 이 문제를 통해 얻어갈 것
플로이드-워셜 기본 코드 작성법.

Java 코드 :

import java.io.*;
import java.util.*;

// 11404 플로이드
public class Main {

	static BufferedReader br;
	static BufferedWriter bw;

	static int n, m;
	static int a, b, c;
	static int[][] dist;

	static final int INF = 20000000;

	static class Edge {
		int target, cost;

		public Edge(int target, int cost) {
			this.target = target;
			this.cost = cost;
		}
	}

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());

		// 1. 거리배열 무한대로 초기화
		dist = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = INF;
			}
		}

		// 2. 양방향 간선으로 입력받기
		StringTokenizer st;
		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());

			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());

			// 새로운 버스 비용이 적은 경우 갱신
			if (c < dist[a][b]) {
				dist[a][b] = c;
			}				
		}

		// 3. 플로이드-워셜 진행
		// 3중 for문 순서 경유 - 출발 - 도착
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					// 기존 (출발-도착) > (출발-경유) + (경유-도착) 이면 갱신
					if (dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}

		// 4. 전체 출력
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i==j) {
					sb.append(0+" ");
				}
				else if (dist[i][j] == INF) {
					sb.append(0+" ");
				}
				else {
					sb.append(dist[i][j]+" ");
				}
			}
			sb.append("\n");
		}
		bw.write(sb.toString());

		bw.flush();
		bw.close();
		br.close();
	}

}