[JAVA] 백준 - 움직이는 미로 탈출 - 16954 ( BFS)

www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

 

미로가 움직이기 때문에 현재 좌표의 상태에 미로가 추가 되어야 한다.

 

즉, 현재 상태를 기억하는 정보에 미로를 추가해야한다.

 

 

 

int 배열로 정보를 만든다면 메모리가 많이 들겠지만 다행히도 boolean 배열로도 정보를 기억할 수 있다. 

또한 미로 역시 8*8 로 크기가 크지 않기 때문에 충분히 미로에 대한 정보를 들고 다녀도 된다.

 

 

# 풀이

1. 현재 위치가 도착지점인가?

    1-1. 도착지점이면 ok = true

    1-2. 도착지점이 아니라면 2번으로

2. 현재 미로판의 다음 상태의 미로판을 구한다.

3. 현재 위치에서 다음 위치로 좌표를 구한다( 8가지 경우의 수)

    3-1. 현재 미로판에서 다음위치는 빈칸 && 다음 미로판에서 다음 위치는 빈칸 && 해당 위치를 방문한 적이 없다면 큐에 넣는다.

4. 현재 위치에서 기다릴 수 있다면 큐에 넣고 기다린다. 단, 8회 이상 기다리지 않는다.

 

 

import java.util.LinkedList;
import java.util.*;

class Main{
    static boolean[][][] ch = new boolean[8][8][8];

    static int[] dx = {-1,1,0,0,-1,-1,1,1};
    static int[] dy = {0,0,-1,1,-1,1,-1,1};

    static boolean ok = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        boolean[][] chess = new boolean[8][8];
        for(int i=0;i<8;i++){
            char[] temp = sc.next().toCharArray();
            for(int j=0;j<8;j++){
                chess[i][j] = temp[j]!='.';
            }
        }

//        for(int i=0;i<8;i++){
//            for(int j=0;j<8;j++){
//                System.out.print(chess[i][j]?1:0);
//            }
//            System.out.println();
//        }


        // start (7,0)
        Queue<Pair> q = new LinkedList<>();
        ch[7][0][0] = true;
        q.add(new Pair(7,0,0,chess));

        while(!q.isEmpty()){
            Pair p = q.poll();

            if(p.x == 0 && p.y == 7) ok=true;

            boolean[][] nextChess = nextChess(p.myChess);
            // 다음 위치로 가기
            for(int i=0;i<8;i++){
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(nx<0 || nx>=8 || ny<0 || ny>=8) continue;

                if(p.myChess[nx][ny]==false && nextChess[nx][ny]==false && ch[nx][ny][p.wait]==false){
                    ch[nx][ny][p.wait] = true;
                    q.add(new Pair(nx,ny,p.wait,nextChess));
                }
            }

            if(p.wait +1 < 8 && nextChess[p.x][p.y]==false){
                ch[p.x][p.y][p.wait+1] = true;
                q.add(new Pair(p.x,p.y,p.wait+1,nextChess));
            }
        }

        System.out.println(ok?1:0);

    }

    static boolean[][] nextChess(boolean[][] chess){
        boolean[][] next = new boolean[8][8];
        for(int i=0;i<7;i++){
            for(int j=0;j<8;j++){
                next[i+1][j] = chess[i][j];
            }
        }
        return next;
    }

    static class Pair{
        int x,y;
        int wait;
        boolean[][] myChess = new boolean[8][8];

        public Pair(int x, int y,int wait,boolean[][] chess) {
            this.x = x;
            this.y = y;
            this.wait = wait;
            for(int i=0;i<8;i++){
                System.arraycopy(chess[i], 0, this.myChess[i], 0, 8);
            }
        }
    }
}