[Java] 백준 11403번 : 경로 찾기

1. 문제

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

11403번: 경로 찾기

 

 

2. 풀이 과정

주어진 input이 인접 행렬이며, 간선의 개수가 많을 수도 있기 때문에 인접 행렬을 사용했다.

또한, 모든 정점에서 모든 정점으로의 경로 여부를 묻고 있어서 플로이드 워샬로 문제를 풀었다.

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

public class Main {
    static int N;
    static int[][] arr;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        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] = st.nextToken().charAt(0) - '0';
            }
        }


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

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                sb.append(arr[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

    }
}

 

 

결과