BOJ 11403 경로 찾기 [Java]

BOJ 11403 경로 찾기

1. 문제 링크

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

2. 문제 해설

플로이드 알고리즘을 이용하면 쉽게 풀 수 있다. 정점의 최대 갯수가 100개이므로 최대 연산 수는 1000000으로 넉넉하게 통과한다.
입력으로 arr배열을 받고 1이 아니면 (Integer.MAX_VALUE - 1) / 2로 초기화해준다. Integer.MAX_VALUE로 초기화할 시 31번째 줄 코드에서 오버플로우가 발생할 수 있다는 점을 주의하자.
그 후 플로이드 과정을 거치고 arr[i][j] 값이 아직 (Integer.MAX_VALUE - 1) / 2 인 곳은 갈 수 있는 경로가 없다는 의미이다.
그러므로 그런 위치는 0, 아닌 곳은 1을 출력해주면 쉽게 해결할 수 있다.

3. 코드 보기

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
 
        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());
 
                if (arr[i][j] == 0) {
                    arr[i][j] = (Integer.MAX_VALUE - 1) / 2;
                }
            }
        }
 
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];  // 여기서 오버플로우가 발생 가능하기에 22번째 줄에서 (Integer.MAX_VALUE - 1) / 2로 처리함.
                    }
                }
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == (Integer.MAX_VALUE - 1) / 2) {
                    sb.append(0 + " ");
                } else {
                    sb.append(1 + " ");
                }
            }
 
            sb.append("\n");
        }
 
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}