[Boj 11403] 경로 찾기
18273 단어 algorithmfloyd-warshallbojalgorithm
📎 문제링크
1. 시간복잡도
정점의 개수 N (1 ≤ N ≤ 100) 으로 을 해도 → 0.013sec 아주 넉넉하다.
💡 플로이드-와샬의 시간복잡도는 O() 이다.
1.2 플로이드-와샬 (Floyd-Warshall)
플로이드-와샬은 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘이다. 기본적인 개념은 삼단논법
과 같다. A->B이고, B->C이므로 A->C가 성립한다.
2. 풀이
2.1 BFS VS Floyd-Warshall
시간복잡도는 BFS도 = O() 로 유사할것이라고 예상되었는데, 제출결과를 보면 메모리 & 시간 그리고 코드길이까지 많이 차이나는 것을 볼 수 있다.
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());
}
}
Author And Source
이 문제에 관하여([Boj 11403] 경로 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@agpine12/Boj-11403-경로-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)