[백준 11403번] 경로 찾기 - JAVA

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

풀이

사용한 알고리즘: 플로이드 워셜(Floyd Warshall)

 

풀이전략

플로이드 워셜 알고리즘을 사용하여 모든 출발지에서 도착지까지의 최단 거리를 구한다.

단, 기존 플로이드 워셜 알고리즘에서는 자기 자신에게 가는 거리를 0으로 두고 알고리즘을 실행했지만

이 문제에서는 거리가 아닌 경로의 유무 판단이 중요 쟁점이기 때문에 모든 배열의 원소를 INF(무한)으로 초기설정한다. 그리고 입력에서 1로 경로가 있는 경우에만 배열 원소를 수정한뒤 플로이드 워셜 알고리즘을 수행해야한다.

 

그리고 나온 결과에서 0이 아닌 수를 가진 값들은 1을 출력하고, INF는 0으로 출력하면 답을 구할 수 있다.

 

제출코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

import static java.lang.String.valueOf;

public class Main {

    static int graph[][];
    static final int INF = 987654321;
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N=Integer.parseInt(br.readLine());

        graph = new int[N][N];

        for(int i=0;i<N;++i)
            Arrays.fill(graph[i],INF);

        for(int i=0;i<N;++i){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;++j){
                if(st.nextToken().equals("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)
                    graph[j][k]=Math.min(graph[j][k],graph[j][i]+graph[i][k]);

        for(int i=0;i<N;++i) {
            for (int j = 0; j < N; ++j) {
                if (graph[i][j] == INF) sb.append(0).append(' ');
                else sb.append(1).append(' ');
            }
            sb.append("\n");
        }
        System.out.println(valueOf(sb));
    }
}