백준 16954번 움직이는 미로 탈출 [JAVA]

문제

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

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

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

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

 

 

입력

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

 

 

출력

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

 

 

예제

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main_BJ_16954_움직이는미로탈출 {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int N=8;
    static int startX = 7, startY = 0, endX=0, endY = 7;
    static Queue<info> person = new LinkedList<>();
    static char [][] map;
    static boolean [][] visited;
    static int [] dx = {0,-1,-1,0,1,1,1,0,-1};
    static int [] dy = {0,0,1,1,1,0,-1,-1,-1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        map = new char[N][N];
        
        for(int i=0;i<N;i++) {
            String str = br.readLine();
            for(int j=0;j<N;j++) {
                map[i][j] = str.charAt(j);
            }
        }
        
        if(bfs()) System.out.println(1);
        else System.out.println(0);
    }
    
    public static boolean bfs() {
        person.add(new info(startX, startY));
        
        while(!person.isEmpty()) {
            visited = new boolean[N][N];
            int size = person.size();
            
            for(int j=0;j<size;j++) {
                
                info in = person.poll();
                
                if(map[in.x][in.y]=='#') continue;
                
                for(int i=0;i<9;i++) {
                    
                    int nx = in.x+dx[i];
                    int ny = in.y+dy[i];
                    
                    if(range(nx,ny)) {
                        if(nx==endX && ny==endY) {
                            return true;
                        }
 
                        if(map[nx][ny]!='#' && !visited[nx][ny]) {
                            person.offer(new info(nx,ny));
                            visited[nx][ny] = true;
                        }    
                    }
                }
            }
            move();
        }
        
        return false;
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<N && y<N;
    }
    
    public static void move() {
        
        for (int i = N-1; i >= 0; i--) { 
            for (int j = 0; j < N; j++) { 
                if(i==0) map[i][j] = '.'; 
                else map[i][j] = map[i-1][j]; 
                } 
        }
    }
}

 

 

-