[JAVA] 백준 11403 플로이드-워셜

 

 

 

 

11403번: 경로 찾기

문제

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

풀이

주어진 정점들에 대해서 다른 모든 정점으로 가는 경로가 있는지 여부에 대한 출력을 하는 문제입니다.

저는 모든 정점들에 대해서 다른 모든 정점으로의 경로 였기 때문에 플로이드-워셜 알고리즘을 사용하여 문제를 해결하였습니다.

📌 입력

        int[][] A = new int[N][N];

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

해당 문제는 가중치는 없고 갈 수 있는지 여부만 나타내는 형식이었기 때문에 입력을 그대로 받아서 2차원 배열에 담아두었습니다.

📌 플로이드-워셜

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

3중 for문을 사용하여 플로이드 워셜 알고리즘을 구현하였습니다.

i → j로 가는 경로가 없을 때, i → k 경로와 k → j 경로가 존재한다면 i → j로 가는 경로가 존재한다는 의미이기 때문에 경로가 존재함을 뜻하는 1을 채워넣었습니다.

📌 출력

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

StringBuilder를 사용하여 System.out.println() 메서드의 사용횟수를 줄였습니다.

📌 전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[][] A = new int[N][N];

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

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

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

    }
}

결과