[백준] 11403번: 경로 찾기 - JAVA

🔗 문제 링크

BOJ 11403번: 경로 찾기

11403번: 경로 찾기

 

📝 풀이 과정

모든 정점에서 다른 정점까지 도달할 수 있는지 탐색할 수 있는지를 판별하는 문제이다. 따라서, 플로이드 와샬 알고리즘을 생각해 볼 수 있는데, 문제에서 N의 범위가 100이하으므로 $O(N^3)$인 플로이드 와샬을 써도 괜찮은 문제이다.

 

k, i, j를 3중 반복문을 통해 탐색하며,

만약 i -> k로 갈 수 있고 k -> j로도 갈 수 있다면, i -> j로 가는 경우가 가능하기 때문에 true로 값을 변경해준다.

 

💻 코드

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

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

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < N; j++)
                map[i][j] = input[j].charAt(0) == '1';
        }

        for (int k = 0; k < N; k++)
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if (map[i][k] & map[k][j])
                        map[i][j] = true;

        StringBuilder sb = new StringBuilder();
        for (boolean[] con : map) {
            for (boolean b : con)
                sb.append(b ? 1 : 0).append(' ');
            sb.append('\n');
        }
        System.out.println(sb.toString());

    }
}

 

📊 제출 결과