11403_경로 찾기

사용 알고리즘: 플로이드-워셜

사용 언어: JAVA

 

 

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

public class Main_11403_findPath {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] 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 i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                for(int k=0; k<n; k++) {
                    if(graph[i][k]==1 && graph[k][j]==1) {
                        graph[i][j] = 1;
                    }
                }
            }
        }
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                for(int k=0; k<n; k++) {
                    if(graph[i][k]==1 && graph[k][j]==1) {
                        graph[i][j] = 1;
                    }
                }
            }
        }

        //
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) {
                System.out.print(graph[i][j]+" ");
            }
            System.out.println();
        }
    }
}

 

 

이슈:

플로이드 워셜을 한 번 돌렸을 때, 건너건너 이어진 곳을 미처 찾지 못하는 문제 발생

-> 단순히 플로이드 워셜을 한 번 더, 총 2번 돌리는 걸로 해결했지만.. 최적화된 방법이 있을 거 같은데

 

 

수정)))

의외로 플로이드 워셜 두 번 돌리는 거보다 최적화된 방법이라고 생각했던 게 더 오래 걸린다..?