[BOJ 11404] 플로이드 (G4)

📍 문제 

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

 

📍 문제 풀이 

 

한 지점에서 다른 지점으로 가는 최단거리라고 하면 다익스트라

시작 노드에서 도착 노드까지 거리를 찾고

최단 거리 노드를 방문하며 시작 노드로부터 경로를 최적화한다. 

이 과정을 모든 노드를 방문할 때까지 한다.

 

이 문제의 경우 문제 이름 자체도 플로이드였기 때문에 플로이드 워셜 방식으로 풀었다.

플로이드 워셜 알고리즘에 대한 정리는 여기에..

 

📍 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_11404 {
	static int n,m;
	static int[][] maps;
	static final int INF = 10000001;

	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());

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

		for (int i = 0; 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());

			maps[start - 1][end - 1] = Math.min(maps[start - 1][end - 1], cost);
		}

		floyd();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				sb.append(maps[i][j] == INF ? 0 : maps[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);

	}

	static void floyd() {
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					maps[i][j] = Math.min(maps[i][k] + maps[k][j], maps[i][j]);
				}
			}
		}
	}
}