[백준] 13565번 : 침투

13565번: 침투

---

[DFS or BFS]

이런 2차원 배열이 주어지는 탐색문제에서 주로 BFS만 사용했어서 이번엔 DFS로 풀어보았다.

 

문제의 답을 도출하는 방법은 매우 단순하다. 첫째 줄에서 출발해서 검은 칸이 아닌 상하좌우 흰색 칸을 따라 마지막 줄까지 도달할 수 있는가?

 

    static boolean DFS(int y, int x){

        if(y == r)
            return true;

        visit[y][x] = true;
        boolean result = false;

        for(int a=0; a<4; a++) {
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx] || map[ny][nx] == '1') continue;

            result |= DFS(ny, nx);
        }

        return result;
    }

DFS는 boolean을 반환한다. 만약 y가 마지막 줄에 도달하면 true를 반환하도록 하고, DFS가 반환하는 값 result는 해당 탐색에서 true를 반환하는 곳이 하나라도 있으면 쭉 true를 유지하도록 설계하였다.

# Code </>

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

public class Main {

    static char[][] map = new char[1001][1001];
    static boolean[][] visit = new boolean[1001][1001];
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int r, c;

    static boolean DFS(int y, int x){

        if(y == r)
            return true;

        visit[y][x] = true;
        boolean result = false;

        for(int a=0; a<4; a++) {
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx] || map[ny][nx] == '1') continue;

            result |= DFS(ny, nx);
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        for(int i=1; i<=r; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=c; j++)
                map[i][j] = str[j-1];
        }

        boolean result = false;
        
        for(int i=1; i<=c; i++)
            if(!visit[1][i] && map[1][i] == '0')
                result |= DFS(1, i);

        System.out.println(result?"YES":"NO");
    }
}