[백준, 자바, 11403번] 경로 찾기

풀이

• 뭔가 메모리 초과나 시간 초과가 발생할 줄 알았지만
• 다행히도 따로 문제가 발생하지 않았음.
• 우선 mtx랑 result를 따로 구분한 건
• mtx를 result랑 똑같이 할 경우 탐색할 것들이 많아질것 같아 구분했음.
• 그리고 다른점은 뭐 dfs니까 visit로 중복 탐색하지 않도록 하는 것 뺴곤
• 다른 2차원 배열 문제와 같이 해결.

 

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class _11403 {
    static int n;
    static int[][] mtx;
    static int[][] result;
    static boolean[][] visit;
    static Deque<Integer> dq;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        mtx = new int[n][n];
        result = new int[n][n];
        dq = new ArrayDeque<>();

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

        for (int i=0; i<n; i++) {
            visit = new boolean[n][n];
            for (int j=0; j<n; j++) {
                if (mtx[i][j]==1) {
                    dq.add(j);
                    visit[i][j] = true;
                    dfs(i);
                }
            }
        }

        for (int[] li: result) bw.write(Arrays.stream(li).mapToObj(String::valueOf).collect(Collectors.joining(" "))+"\n");
        bw.flush();
    }

    public static void dfs(int now) {
        while (!dq.isEmpty()) {
            int dj = dq.pollFirst();
            for (int k=0; k<n; k++) {
                if (mtx[dj][k]==1 && !visit[dj][k]) {
                    dq.add(k);
                    result[now][k] = 1;
                    visit[dj][k] = true;
                }
            }
        }
    }
}