11403번: 경로 찾기

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

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다.

i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다.

정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 1

3
0 1 0
0 0 1
1 0 0

예제 출력 1

1 1 1
1 1 1
1 1 1

예제 입력 2

7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0

예제 출력 2

1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 0 0 0 0 0
1 0 1 1 1 1 1
1 0 1 1 1 1 1
0 0 1 0 0 0 1
0 0 1 0 0 0 0

풀이

package graph_search;

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

public class Main_11403 {

    private static int numberOfVertex;
    private static int[][] oneDirection;
    private static int[][] result;

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        numberOfVertex = Integer.parseInt(st.nextToken());

        oneDirection = new int[numberOfVertex + 1][numberOfVertex + 1];
        result = new int[numberOfVertex + 1][numberOfVertex + 1];

        for (int y = 1; y <= numberOfVertex; y++) {
            st = new StringTokenizer(br.readLine());

            for (int x = 1; x <= numberOfVertex; x++) {
                oneDirection[x][y] = Integer.parseInt(st.nextToken());
            }
        }
    }

    private static void process() {
        for (int start = 1; start <= numberOfVertex; start++) {
            int[] canGo = new int[numberOfVertex + 1];
            boolean[] visited = new boolean[numberOfVertex + 1];

            dfs(start, canGo, visited);      // canGo 초기화

            for (int destination = 1; destination <= numberOfVertex; destination++) {
                if (canGo[destination] == 1) {
                    result[start][destination] = 1;
                }
            }
        }
    }

    private static void dfs(int start, int[] canGo, boolean[] visited) {
        for (int destination = 1; destination <= numberOfVertex; destination++) {
            if (oneDirection[start][destination] == 1 && !visited[destination]) {
                canGo[destination] = 1;
                visited[destination] = true;

                dfs(destination, canGo, visited);
            }
        }
    }

    private static void output() {
        StringBuilder sb = new StringBuilder();

        for (int y = 1; y <= numberOfVertex; y++) {
            for (int x = 1; x <= numberOfVertex; x++) {
                sb.append(result[x][y]).append(" ");
            }

            sb.append("\n");
        }

        System.out.println(sb);
    }

}