062 : 경로 찾기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
가중치 없는 방향 그래프 G 모든 노드쌍(i, j) 경로 여부 탐색	플로이드-워셜	I //  노드 갯수 N (1) 인접 행렬 1 or 0 ... (3) 인접 행렬 O // 인접 행렬로 출력(0 or 1)

*i번째 줄 i 수는 항상 0

 

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

public class Main {

    // Input Supply Cable
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int D[][];

    public static void main(String[] args) throws IOException {

        // Preprocessing
        N = Integer.parseInt(br.readLine());
        D = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int v = Integer.parseInt(st.nextToken());
                D[i][j] = v;
            }
        }

        // Operating floyd-warshall
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (D[i][k] == 1 && D[k][j] == 1)
                        D[i][j] = 1;
                }
            }
        }

        // Output Extracting Cable
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(D[i][j] + " ");
            }
            System.out.println();
        }
    }

}