[백준] 11403번. 경로 찾기(JAVA)

문제

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

---

풀이(7분)

import java.io.*;
import java.util.*;

public class Main {


    static int n;
    static boolean[][] floyd;

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

        n = Integer.parseInt(br.readLine()); // 정점의 개수

        floyd = new boolean[n+1][n+1]; // 인덱스를 편리하게 사용하기 위해 +1
        for(int i = 1; i <= n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++){
                int check = Integer.parseInt(st.nextToken());
                if(check == 1){ // 경로가 존재하는 경우
                    floyd[i][j] = true;
                }
            }
        }

        floyd(); // 플로이드-와샬 알고리즘

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++) {
                if(floyd[i][j]){
                    sb.append("1").append(" ");
                }else{
                    sb.append("0").append(" ");
                }
            }
            sb.append("\n");
        }

        System.out.println(sb);

    }

    static void floyd(){
        for(int k = 1; k<= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    floyd[i][j] = (floyd[i][j] || (floyd[i][k] && floyd[k][j])) ? true : false; // 원래 갈 수 있거나, 거쳐가는 것이 가능한 경우
                }
            }
        }
    }


}

 

---

문제 풀이 전략

 

플로이드-와샬 알고리즘의 하위 버전 문제라고 생각한다.

여기서 중요한 것은 n = 100이 최대라는 것을 인식하여 3중 포문을 사용해도 10^6 = 1_000_000으로 충분한 연산이 가능하다는 것이다.

그것만 깨달았다면 모든 좌표에 대해 두 가지를 확인해 주면 된다.

i -> j로 갈 때, 기존의 i -> j가 존재하는지 or i -> k -> j로 거쳐가는 경로가 존재하는지이다.

for 반복문을 보면 1번 정점에서 1~n 정점까지 1~n을 거쳐가는 경로가 모두 확인되게 된다.

 

더욱 추가적인 문제를 원한다면

2025.04.01 - [문제 풀이/도구정리] - [도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

[도구정리] 플로이드-와샬(Floyd-Warshall) 알고리즘

알고리즘을 참고하자.

 

또한, 백준 10404 문제도 꼭 풀어보자!