정점의 개수 N (1 ≤ N ≤ 100) 으로 을 해도 → 0.013sec 아주 넉넉하다.
💡 플로이드-와샬의 시간복잡도는 O() 이다.
플로이드-와샬은 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘이다. 기본적인 개념은 삼단논법
과 같다. A->B이고, B->C이므로 A->C가 성립한다.
시간복잡도는 BFS도 = O() 로 유사할것이라고 예상되었는데, 제출결과를 보면 메모리 & 시간 그리고 코드길이까지 많이 차이나는 것을 볼 수 있다.
package week12;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Boj_11403_2 {
static int N;
static int[][] ans;
static Map<Integer, ArrayList<Integer>> edge = new HashMap<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
ans = new int[N][N];
ArrayList<Integer> t;
for (int i = 0; i < N; i++) {
ans[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
// Floyd-Warshall
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(ans[i][k] == 1 && ans[k][j] == 1) {
ans[i][j] = 1;
}
}
}
}
// print
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(ans[i][j] + " ");
}
sb.deleteCharAt(sb.length()-1);
sb.append("\n");
}
System.out.println(sb.toString());
}
}