백준 No.11403 경로 찾기 - JAVA

문제

가중치 없는 방향 그래프 G가 주어졌을 떄, 모든 정점 (i,j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오

 

3
0 1 0
0 0 1
1 0 0

 

풀이

- 인접행렬로 받아 인접행렬로 출력하고, 바로 플로이드 와샬이 떠오르긴 했는데 바로 적용하기가 어려웠다.. 

0,0 부분만 0이 출력되는 결과가 나와버려서 해결 못해서 답을 찾아봤다.

결국 arr[2번쨰 for][1번째 for]==1 && arr[1번째 for][3번쨰 for] 가 통과하면 arr[2번쨰 for][3번쨰 for] 로 갈 수 있다는 뜻이므로 arr[2번쨰 for][3번쨰 for]에 1을 넣어주면 정답이다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        int arr[][] = new int[N][N];

        for (int i = 0; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N ; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N ; i++) {
            for (int j = 0; j < N ; j++) {
                for (int k = 0; k < N ; k++) {
                    if(arr[j][i] == 1 && arr[i][k] == 1){
                        arr[j][k] = 1;
                    }
                }
            }
        }

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

    }
}