[백준 16954번] 움직이는 미로 탈출(java)

문제

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

---

정답

처음에는 이 문제를 너비탐색(BFS)로 풀었다. 푸는 단계는

1. 체스판 정보를 2차원배열에 저장
2. 시작 지점에 정보를 Queue에 삽입
3. Queue가 빌때까지 반복 대신 반복할때마다 Queue.size() 만큼 반복 Queue.size()만큼의 반복이 끝나면 벽을 한칸 내림
4. 다시 Queue가 빌때까지 반복

이런식으로 문제를 풀었다. 근데 시간도 너무 오래걸리고 메모리도 너무 잡아먹었다. 특히 문제의 요지는 맨위오른쪽에 도착할수있는가? 를 찾는 문제인데 너비탐색은 옳지 않은것 같았다. 그래서 DFS깊이 탐색으로 풀기로 했다.

깊이탐색으로 풀려면 어떻게 해야하나 생각했다. 아무리 생각해봐도 벽의 변화를 미리 알아야할것같았다.
이 문제에서는 체스판의 사이즈가 8x8이기 때문에 벽의 변화는 8번 밖에 일어나지 않는다.

1. 체스판의 정보를 board[][][0]에 저장한다.
2. 체스판의 벽이 변화한 정보들을 단계별로 board[][][step(1~7)]에 저장한다.
3. dfs()를 돌면서 인자로 step의 정보를 같이 넘겨주면서 벽의 위치를 계산한다.
4. 현재 위치가 맨위 행까지 닿는다면 목표지점에 닿을수 있기 때문데 true를 리턴하고 끝낸다.

위 방식대로 푸니 간단하게 풀렸다.
처음에는 벽의 변화하는 모든 정보를 미리 저장하는것 자체가 비효율적인 풀이라고 생각해서 저장하지 않았다. 하지만 어느정도 사이즈가 작은 수준에서는 미리 저장해놓는 것이 더 빠르다는 것을 알게되었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


public class Main {
    private static int[] dY = new int[] {0,-1,0,1,1,-1,-1,1,0};
    private static int[] dX = new int[] {-1,0,1,0,1,1,-1,-1,0};
    private static final int SIZE = 8;
    private static final char BLANK = '.';

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException{
        char[][][] board = new char[SIZE][SIZE][SIZE];
        for(int row = 0; row<SIZE; row++) {
            String line = br.readLine();
            for(int col = 0 ; col<SIZE; col++) {
                board[row][col][0] = line.charAt(col);
            }
        }

        //step:0 = 체스판변화x
        //step:1 = 체스판변화 1회
        //step:2 = 체스판변화 2회
        for(int step=1 ; step<SIZE; step++) {
            for(int row=0; row<SIZE-1; row++) {
                for(int col=0; col<SIZE; col++) {
                    board[row+1][col][step] = board[row][col][step-1];
                }
            }
            for(int col=0; col<SIZE; col++) {
                board[0][col][step]= BLANK;
            }
        }
        //깊이탐색으로 검색 dfs(시작위치좌표y,시작위치좌표x,체스판,step) 
        if(dfs(SIZE-1,0,board,0)) {
            bw.append('1');
        }else {
            bw.append('0');
        }

        bw.flush();
        return;

        //printBoard(board);
    }
    //step이 SIZE와 같아지면 끝에 닿을수 있다는 의미임
    public static boolean dfs(int y, int x, char[][][] board, int step) {
        if(step+1 == SIZE) {
            return true;
        }

        for(int i=0;i<9;i++) {
            int nextx = x+dX[i];
            int nexty = y+dY[i];
            if(nexty<0 || nexty>=SIZE || nextx<0 || nextx>=SIZE)
                continue;
            //다음 칸이 빈칸이고 다음 step칸도 빈칸이면 dfs진행
            if(board[nexty][nextx][step]==BLANK && board[nexty][nextx][step+1]==BLANK) {
                if(dfs(nexty,nextx,board,step+1)) {
                    return true;
                }
            }
        }
        return false;
    }
    public static void printBoard(char[][][] board) {
        for(int i=0;i<SIZE;i++) {
            for(int j=0;j<SIZE;j++) {
                for(int k=0;k<SIZE;k++) {
                    System.out.print(board[j][k][i]);
                }
                System.out.println();
            }
            System.out.println("=================");
        }
    }
}