[BOJ] 13565 침투

침투

풀이

• 입력의 첫행에서 0인 곳에서만 탐색을 시작할 수 있기 때문에 Queue를 선언해서 시작점 후보들을 저장함.
• dfs를 이용해서, 각 시작점에서 시작하여 마지막 행의 0인 후보들에 도착할 수 있는지 확인함
• 실행시간이 많이 걸림 -> bfs로 풀면 더 적게 걸리는 듯?

코드

import java.util.*;
import java.io.*;

public class BOJ13565 {
    static char[][] map;
    static boolean[][] visited;
    static boolean isFind = false;
    static int M, N;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static Queue<int[]> startQ = new LinkedList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        
        map = new char[M][N];
        
        
        for (int i = 0; i < M; i++) {
            String input = br.readLine();
            map[i] = input.toCharArray();
        }

        //시작점 후보 Q에 넣기
        for (int j = 0; j < N; j++) {
            if (map[0][j] == '0') {
                startQ.offer(new int[] { 0, j });
            }
        }

        //시작점이 없는 경우 NO 출력
        if (startQ.size() == 0) {
            System.out.println("NO");
        }
        else {
            boolean isFind = false;
            while (!startQ.isEmpty()) {
                isFind = false;
                visited = new boolean[M][N];
                int[] cur = startQ.poll();
                int startX = cur[0];
                int startY = cur[1];
                isFind = dfs(startX, startY);
                if (isFind)
                    break;
            }
            if (!isFind) {
                //다 돌았는데도 없으면 NO
                System.out.println("NO");
            }
            else {
                System.out.println("YES");
            }
        }

    }

    private static boolean dfs(int x, int y) {

        visited[x][y] = true;
        if (x == M - 1 && map[x][y] == '0') {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < M && ny >= 0 && ny < N && map[nx][ny] == '0' && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
        return false;
    }
}