풀이

플로이드와샬 알고리즘을 사용하는 굉장히 기본적인 문제이다.
분명 알고리즘 수업시간에 배운 기억은 있는데 뭐였는지는 잘 기억이 안나 찾아보았다.

간략히 말하면 플로이드와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
기본적으로 DP를 사용한다.
i가 출발점, j가 도착점이라고 할 때, 중간에 k를 거쳐서 i에서 j까지 도달하는 최단 거리를 구한다고 할 수 있다.

코드를 보면 이해하기 더 쉬울 것이다.

public static void floyd() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
    }

i에서 j까지 한 번에 가는 거리와 i -> k, k -> j로 중간에 k를 거치는 경로가 거리를 비교하며 더 작은 값으로 업데이트 하는 방식이다.

다시 풀이로 돌아가자면, 여기서는 거리를 구하는 것이 아닌 경로가 있는지 여부만 확인하면 되기 때문에 i -> k, k -> i 가 가능하다면 map의 값을 1로 바꿔주면 된다.

코드

package BOJ;

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

public class sol11403 {
    static int n;
    static int[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];

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

        floyd();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }

    }

    public static void floyd() {
        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] == 1 && map[k][j] == 1) {
                        map[i][j] = 1;
                    }
                }
            }
        }
    }
}