[Boj 11403] 경로 찾기

eunsol Jo·2021년 10월 1일
0

🧁  Algorithm

목록 보기
4/4
post-thumbnail

📎 문제링크

1. 시간복잡도

정점의 개수 N (1 ≤ N ≤ 100) 으로 N3N^3 을 해도 10610^6 → 0.013sec 아주 넉넉하다.

💡 플로이드-와샬의 시간복잡도는 O(N3N^3) 이다.

1.2 플로이드-와샬 (Floyd-Warshall)

플로이드-와샬은 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘이다. 기본적인 개념은 삼단논법과 같다. A->B이고, B->C이므로 A->C가 성립한다.

2. 풀이

2.1 BFS VS Floyd-Warshall


시간복잡도는 BFS도 N2(2N+N)N^2*(2N+N) = O(N3N^3) 로 유사할것이라고 예상되었는데, 제출결과를 보면 메모리 & 시간 그리고 코드길이까지 많이 차이나는 것을 볼 수 있다.

3. 유사문제

4. 코드

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

    }
}
profile
Later never comes 👩🏻‍💻

0개의 댓글