[Java] 11403번. 경로 찾기 (# 플로이드-워셜)

문제링크 : https://www.acmicpc.net/problem/11403

i번째 점에서 j번째로 가는 경로가 있는지 탐색
(인접행렬을 구하는 것이 아니라 경로행렬을 구하는 것)

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

public class Main {

    public static int n;
    public static boolean[][] map; //i에서 j 경로가 있는지 담는 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        map = new boolean[n][n];
        for (int i = 0 ; i < n ; i ++){ //입력 그래프를 map에 저장
             st = new StringTokenizer(br.readLine());
             for(int j = 0 ; j < n ; j++) {
                 if(Integer.parseInt(st.nextToken()) == 1) map[i][j] = true;
             }
        }
        for(int i = 0 ; i < n ; i++){ //연결되어있다면 추가경로도 탐색 fw(i,j)
            for(int j = 0 ; j < n ; j++){
                if(map[i][j] == true) fw(i,j);
            }
        }
        
        //출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0 ; i < n ; i++){
            for (int j = 0 ; j < n ; j++){
                if(map[i][j] == true) sb.append("1 ");
                else  sb.append("0 ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
   	
    //추가경로 탐색 fw(i,j)
    //i에서 j가 연결되어있다면,
    //j에서 k로 가는 경로를 찾아 i에서 k로 가는 경로도 있는 것으로 판단
    //그리고 fw(i,k) 실행 (dfs 이용)
    public static void fw(int i, int j){
        for(int k = 0 ; k < n ; k++){
            if(map[j][k] == true && map[i][k] == false) {
                map[i][k] = true;
                fw(i,k);
            }
        }

    }
}