[백준/13565] 침투 - JAVA

📌 문제

알고리즘 분류 : 그래프
난이도 : 실버2
출처 : 백준 - 침투

🦧 문제 풀이 접근

2차원 배열에서 i=0인 부분과 붙어있는 모든 칸을 DFS를 통해 색칠 해간다.
이때 i=M-1인 부분까지 도착한다면 YES, 모든 칸은 다 돌아봤지만 도착하지 않는다면 NO를 출력한다.

💻 code

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

public class Main {
    static boolean[][] arr;
    static boolean check = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        arr = new boolean[M][N];
        for(int i =0;i<M;i++) {
            String line = br.readLine();
            for(int j=0; j<N; j++) {
                arr[i][j] = line.charAt(j)=='1'?true:false;
            }
        }
        for(int i=0;i<N;i++) {
            if(arr[0][i]==false) {
                req(0,i);
            }
        }
        System.out.println(check?"YES":"NO");
    }

    private static void req(int iIndex, int jIndex) {
        if(iIndex<0 || iIndex>arr.length-1 || jIndex<0 || jIndex>arr[0].length-1)
            return;
        if(arr[iIndex][jIndex])
            return;
        if(iIndex==arr.length-1) {
            check=true;
            return;
        }
        arr[iIndex][jIndex]=true;
        req(iIndex+1,jIndex);
        req(iIndex-1,jIndex);
        req(iIndex,jIndex-1);
        req(iIndex,jIndex+1);
    }
}

🥇 결과

🎓 느낀점

처음에는 미로 찾기 문제라고 생각해서 BFS를 사용해야 될거라고 생각했지만 결국 관련된 모든 칸을 찾는 문제기 때문에 BFS, DFS 모두 상관이 없다.