[백준/자바] 11404번: 플로이드

문제

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

풀이

• n개의 도시
• m개의 버스
• 각 버스는 한 번 사용할 때 필요한 비용 존재
• 모든 도시의 쌍 (a, b)에 대해서 도시 a에서 b로 가는데 필요한 비용의 최솟값

플로이드-워셜 알고리즘

Floyd-Warshall

• 모든 정점 쌍 최단 경로 알고리즘
• 하나의 시작점에서 모든 최단 거리
• 가중치가 있는 방향/무방향 그래프, 음수 간선 가능

점화식

dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

• 즉, "정점 k를 경유하는 경우"가 기존 i -> j 거리보다 짧으면 갱신
• 모든 정점 k-1, k, ..., N에 대해 차례로 반복
  -> 최종적으로 모든 쌍 최단 거리 완성

전형적인 플로이드-워셜 문제입니다.
"최단" 거리를 구해줘야 하기 때문에, 모든 정점의 거리를 최댓값으로 채워 줍니다.

		dist = new int[n+1][n+1];
		for (int i = 1; i <= n; i++) {
			Arrays.fill(dist[i], INF);
			dist[i][i] = 0;
		}

여기서 자기 자신과의 거리는 0으로 초기화해 줍니다.

		for (int i = 0; i < m; i++) {
			StringTokenizer 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] = Math.min(dist[a][b], c);
		}

(a, b)에 대한 거리 c를 입력

	private static void floyd() {
		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];
					}
				}
			}
		}	
	}

모든 거리를 입력을 받았다면, 위 알고리즘을 이용해 최단 거리를 갱신해 줍니다.

마지막으로 입력한 최단 거리들을 차례로 출력해 주면 끝

코드

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

public class Main_11404 {
	static StringBuilder sb = new StringBuilder();
	static int n, m;
	static int[][] dist;
	static final int INF = (int) 1e9;
	
	private static void floyd() {
		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];
					}
				}
			}
		}	
	}
	
	private static void printDist() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				sb.append(dist[i][j] == INF ? 0 : dist[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		dist = new int[n+1][n+1];
		for (int i = 1; i <= n; i++) {
			Arrays.fill(dist[i], INF);
			dist[i][i] = 0;
		}
		
		
		for (int i = 0; i < m; i++) {
			StringTokenizer 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] = Math.min(dist[a][b], c);
		}
		
		floyd();
		printDist();
	}
}