[백준문제풀이] 11404 플로이드 java풀이

접근법 : 

**1) 어떻게 풀 것인가?**

플로이드 워셜을 사용한 문제 

알고리즘 특강때 플로이드 워셜에 대해 설명을 듣고 나서 푼거라 어려운점은 없었다. 

 

**2) 시간복잡도**

O(n^3)인데 n의 최댓값이 100이고, 이 문제는 1초의 제한시간을 가지므로 

제한시간안에 가능하다.

 

**3) 공간복잡도**

256mb

 

**4) 풀면서 놓쳤던점**

딱히 없다!!-

 

**5) 이 문제를 통해 얻어갈 것**

플로이드 워셜이 무엇인지/ 어떻게 풀어야하는지에 대한 감

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

public class Main {

	static int infinite = 200000000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.valueOf(br.readLine());
		int m = Integer.valueOf(br.readLine());
		int[][] dist = new int[n + 1][n + 1];
		
		//최댓값으로 초기화
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				dist[i][j] = infinite;
			}
		}
	
		for (int i = 0; i < m; i++) {
			String[] strings = br.readLine().split(" ");
			int start = Integer.valueOf(strings[0]);
			int end = Integer.valueOf(strings[1]);
			dist[start][end] = Math.min(dist[start][end], Integer.valueOf(strings[2]));
		}
		
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					// (출발 -도착) 와 (출발- 경유 + 경유 - 도착) 중 더 작은 값.
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
	
		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] == infinite) {
					sb.append("0" + " ");
				}
				else {
					sb.append(dist[i][j] + " ");
				}
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}