floyd warshall :: 백준 :: 경로 찾기 :: 11403

경로 찾기 11403

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

[문제 풀이]

이 문제를 푸는 방법은 여러 가지가 있다. 

나는 bfs, dfs, 플로이드 와샬 알고리즘 중 플로이드 와샬 알고리즘을 이용해 풀었다.

플로이드와샬 알고리즘은 형태가 정해져있기 때문에 모든 경로를 탐색하는 문제에 적용하기 쉬운 것 같다.

   1. 모든 입력은 0과 1로 이루어져있다. 나는 입력을 받은 후 int형으로 바꾸지 않고 String형 그대로 map에 저장했다.

   2. 정점 r에서 k로 가는 경로가 존재하고, 정점 k에서 c로 가는 경로도 존재한다면 

      정점 r에서 c로 가는 경로 또한 존재한다고 볼 수 있기 때문에 map[r][c]를 1로 설정해 주면 된다.

   3. 탐색을 모두 마치고 출력하면 끝.

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static String[][] map = new String[100][100];
    static int N;
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().split(" ");
        }
 
        for(int k = 0; k < N; k++){
            for(int r = 0; r < N; r++){
                for(int c = 0; c < N; c++){
                    if(map[r][k].equals("1") && map[k][c].equals("1") && map[r][c].equals("0")){
                        map[r][c] = "1";
                    }
                }
            }
        }
 
        StringBuffer sb = new StringBuffer();
        for(int r = 0; r < N; r++){
            for(int c = 0; c < N; c++){
                sb.append(map[r][c]+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}