[BOJ_11403 | Floyd] 경로 찾기

풀이

플로이드 와샬 알고리즘을 이용해서 각 점의 경로 여부를 확인하면 간단하게 해결할 수 있는 문제였다.

플로이드 와샬 알고리즘이란 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘으로, 

Kruscal, Prim알고리즘과는 달리 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리할 수 있다는 장점이 있다.

하지만, 반복문을 3번 돌리기 때문에 O(n^3)의 시간복잡도를 가지므로 이 점은 유의해야 한다.

3개의 반복문은 각각 다음과 같다.

첫 번째 - 거쳐가는 점

두 번째 - 출발하는 점

세 번째 - 도착하는 점

위 문제는 경로가 있는지 유무만 판단하는 것이므로 초기값을 100이상의 값으로 설정하고

플로이드 와샬 알고리즘을 수행하여 거리를 저장한 배열의 값이 100 이상이면 

경로가 없는 것으로 간주하면 쉽게 해결할 수 있다.

소스 코드

import java.util.*;
public class BOJ_11403 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[][] dis = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int k = input.nextInt();
                if(k == 0) dis[i][j] = 1000;
                else dis[i][j] = k;
            }
        }
        //Floyd & Washall's
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(dis[i][j] > dis[i][k]+dis[k][j])
                        dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
        //print
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dis[i][j] < 1000) System.out.print(1+" ");
                else System.out.print(0+" ");
            }System.out.println();
        }
    }
}