백준 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으로 출력해야 한다.

구현

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

public class Main {
	static StringBuilder builder = new StringBuilder();

	public static boolean DFS(int[][] graph, int start_vertex, int last_vertex) {
		HashSet<Integer> visited = new HashSet<>();
		Stack<Integer> will_visit = new Stack<>();
		will_visit.push(start_vertex);
		int count =0;
		while (will_visit.isEmpty() == false) {
			Integer current_vertex = will_visit.pop();
			if (count!=0&&current_vertex == last_vertex)
				return true;
			for (int i = 0; i < graph.length; i++) {
				if (graph[current_vertex][i] == 1 && !visited.contains(i)) {
					will_visit.add(i);
					visited.add(i);
				}
			}
			count++;
		}
		return false;
	}

	static void areaCount(int[][] graph, int start_vertex) {
		for (int i = 0; i < graph.length; i++) {
			for (int j = 0; j < graph.length; j++) {
				if (DFS(graph, i, j))
					builder.append(1 + " ");
				else
					builder.append(0 + " ");
			}
			builder.append("\n");
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(reader.readLine());
		StringTokenizer tokenizer;
		int[][] nums = new int[N][N];
		for (int i = 0; i < N; i++) {
			tokenizer = new StringTokenizer(reader.readLine());
			for (int j = 0; j < N; j++) {
				nums[i][j] = Integer.parseInt(tokenizer.nextToken());
			}
		}
		areaCount(nums, 0);
		System.out.println(builder);
	}
}

다른 분 구현

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

public class Main {
    static BufferedReader bufferedReader;
    static PrintWriter printWriter;
    static StringTokenizer stringTokenizer;

    static int n;
    static boolean[][] edgeMatrix;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        printWriter = new PrintWriter(System.out);

        n = getNextInt();
        edgeMatrix = new boolean[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                edgeMatrix[i][j] = getNextInt() == 1;

        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited, false);
            for (int j = 0; j < n; j++)
                if (edgeMatrix[i][j] && !visited[j])
                    dfs(j);

            for (int j = 0; j < n; j++)
                printWriter.print(visited[j] ? "1 " : "0 ");
            printWriter.println();
        }

        bufferedReader.close();
        printWriter.close();
    }

    static void dfs(int node) {
        visited[node] = true;
        for (int i = 0; i < n; i++)
            if (edgeMatrix[node][i] && !visited[i])
                dfs(i);
    }

    static int getNextInt() throws IOException {
        return Integer.parseInt(getNextStringToken());
    }

    static String getNextStringToken() throws IOException {
        if (stringTokenizer == null || !stringTokenizer.hasMoreTokens())
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        return stringTokenizer.nextToken();
    }

}