[JAVA-자바] 11403번: 경로 찾기

 

소스코드:

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        boolean[][] graph = new boolean[N][N];

        for (int y = 0; y < N; y++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int x = 0; x < N; x++) {
                graph[y][x] = st.nextToken().equals("1");
            }

        }

        /*
        // solve Floyd-warshall
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    graph[i][j] = graph[i][j] || graph[i][k] && graph[k][j];
                }
            }
        }
        */

        // solve dfs
        for (int start = 0; start < N; start++) {
            boolean[] visited = new boolean[N];
            dfs(start, graph, visited);
            for (int check = 0; check < N; check++) {
                if (visited[check]) {
                    graph[start][check] = true;
                }
            }
        }


        /*
        // solve bfs
        for (int start = 0; start < N; start++) {
            boolean[] visited = new boolean[N];
            Queue<Integer> queue = new LinkedList<>();
            queue.add(start);

            while (!queue.isEmpty()) {
                int current = queue.poll();

                for (int next = 0; next < N; next++) {
                    if (graph[current][next] && !visited[next]) {
                        visited[next] = true;
                        graph[start][next] = true;
                        queue.add(next);
                    }
                }
            }
        }
        */

        // write
        StringBuilder sb = new StringBuilder();
        for (boolean[] temp : graph) {
            for (boolean flag : temp) {
                sb.append(flag ? "1 " : "0 ");
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.close();
    }

    private static void dfs(int current, boolean[][] graph, boolean[] visited) {
        for (int next = 0; next < graph.length; next++) {
            if (graph[current][next] && !visited[next]) {
                visited[next] = true;
                dfs(next, graph, visited);
            }
        }
    }
}

 

폴로이드 워셜/DFS/BFS 3가지 방법으로 풀이하였습니다.

글의 내용 중 잘못된 점이나 수정이 필요한 부분, 혹은 궁금한 사항이 있다면 언제든 댓글로 남겨주시면 감사하겠습니다.

여러분의 피드백은 더 나은 글을 작성하는 데 큰 도움이 됩니다. 감사합니다.