백준 11403
"모든 노드" 간에 최단 경로 탐색
음수 가중치 에지가 있어도 수행할 수 있음(음수사이클X)
동적 계획법의 원리를 이용해 알고리즘에 접근
시간복잡도 O(V^3) - 꽤 느림(N=1000 X)
오히려 N이 작을 때 플로이드 워셜 고려
A->K->B가 최단 경로면 A->K, k->B도 최단 경로이다.
= 3중 for문
실질적으로 최단 경로 배열 D[][] 하나만 구현
import java.util.*;
public class Main {
public static int N;
public static int[][] graph;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
graph = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
graph[i][j] = sc.nextInt();
}
}
for (int k = 0; k < N; k++) {
for (int s = 0; s < N; s++) {
for (int e = 0; e < N; e++) {
if (graph[s][k] + graph[k][e] == 2) {
graph[s][e] = 1;
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(graph[i][j] + " ");
}
System.out.println();
}
sc.close();
}
}