백준 18224 (미로에 갇힌 건우) - java

https://www.acmicpc.net/problem/18224

18224번: 미로에 갇힌 건우

 

문제

평소 탱자탱자 놀던 건우가 마지막 날에 과제를 시작했다. 건우는 피곤이 몰려왔는지, 그만 잠이 들고 말았다! 그러고는 꿈을 꿨다. 그곳은 미로였는데 너무 현실성이 없었던 탓에 건우는 꿈이란 걸 알아챘다. 얼른 꿈에서 깨려고 노력했지만 깰 수 없었다. 왜냐하면 건우가 꿈에서 깨어나려면 반드시 미로를 탈출해야만 했기 때문이다. 미로의 특징은 다음과 같다.

• n×n미로이며 가장 왼쪽 위가 출발지, 가장 오른쪽 아래가 도착지이다. 출발지와 도착지에는 벽이 없음이 보장된다.
• 건우는 상하좌우로만 움직일 수 있으며, 벽을 넘는 것을 제외하면 한 번 이동할 때 벽이 없는 인접한 칸으로 이동한다.
• 초기 상태는 첫 번째 날 낮으로 시작하고, 건우가 m번 이동할 때 마다 낮에서 밤 또는 밤에서 낮으로 바뀐다.
• 밤에는 낮과 달리 추가로 벽을 넘을 수 있다. 벽을 넘을 때는 가려는 방향의 인접한 칸에 벽이 있어야 하며, 건우가 서 있을 수 있는 칸이 나올때까지 연속된 벽을 넘는다.
• 벽을 넘는 도중에 방향을 바꿀 순 없으며, 벽을 넘으면 1번 이동한 것으로 간주한다.

위 경우처럼 벽을 넘었을 때 미로를 벗어날 경우에는 이동할 수 없다.

건우가 가장 빨리 탈출할 수 있는 날이 몇 번째 날의 낮 혹은 밤인지를 구해서 건우가 잠에서 깨도록 만들자!

 

유형 : BFS

 

접근 방식

• 해당 문제를 해결하기 위해 가장 중요한 것은 방문 배열을 어떻게 선언하는가이다.
  • 방문 배열에 있어 고려해야 할 요소는 2가지이다.
    • 낮인가 ? , 밤인가 ?
    • 움직임이 몇번 이루어졌는가?
  • 메모리 초과를 고려해서 boolean 배열로 선언해야 한다.

 

전체 코드

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

public class Main {

    static int resultDay = -1;
    static int isSun = 0;
    static int n,m;
    static int[][] board;

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

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][n+1];

        for(int i = 1 ; i <= n ; i++){
            st = new StringTokenizer(br.readLine()," ");

            for(int j = 1 ; j <= n ; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs();
        if(resultDay == -1){
            System.out.println(-1);
        }else{
            System.out.println(resultDay+" "+(isSun == 0 ? "sun" : "moon"));
        }

        br.close();
    }

    static void bfs(){
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> {
                    if(x.day == y.day){
                        if(x.isDay == y.isDay){
                            return x.move - y.move;
                        }
                        return x.isDay - y.isDay;
                    }

                    return x.day - y.day;
                }
        );

        pq.add(new Node(1,1,1,0,0));

        boolean[][][][] v = new boolean[n+1][n+1][2][m+1];
        v[1][1][0][0] = true;

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(cur.x == n && cur.y == n){

                if(resultDay == -1 || resultDay > cur.day){
                    resultDay = cur.day;
                    isSun = cur.isDay;
                }

                else if(resultDay == cur.day){
                    if(isSun == 1){
                        isSun = cur.isDay;
                    }
                }

                break;
            }

            if(cur.isDay == 0){
                for(int i = 0 ; i < 4 ; i++){
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];

                    if(isOut(nx,ny))
                        continue;

                    if(board[nx][ny] == 1)
                        continue;

                    int tmpMove = cur.move + 1;

                    if(tmpMove == m){
                        if(!v[nx][ny][1][0]){
                            v[nx][ny][1][0] = true;
                            pq.add(new Node(nx,ny,cur.day,0,1));
                        }
                    }else{
                        if(!v[nx][ny][0][tmpMove]){
                            v[nx][ny][0][tmpMove] = true;
                            pq.add(new Node(nx,ny,cur.day,tmpMove,0));
                        }
                    }
                }
            }else{
                for(int i = 0 ; i < 4 ; i++){
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];

                    if(isOut(nx,ny))
                        continue;

                    int tmpMove = cur.move + 1;

                    if(board[nx][ny] == 0){
                        if(tmpMove == m){
                            if(!v[nx][ny][0][0]){
                                v[nx][ny][0][0] = true;
                                pq.add(new Node(nx,ny,cur.day + 1,0,0));
                            }
                        }else{
                            if(!v[nx][ny][1][tmpMove]){
                                v[nx][ny][1][tmpMove] = true;
                                pq.add(new Node(nx,ny,cur.day,tmpMove,1));
                            }
                        }
                    }else{
                        int idx = findJump(nx,ny,i);

                        if(idx == -1)
                            continue;

                        nx = nx + idx*dx[i];
                        ny = ny + idx*dy[i];


                        if(tmpMove == m){
                            if(!v[nx][ny][0][0]){
                                v[nx][ny][0][0] = true;
                                pq.add(new Node(nx,ny,cur.day + 1,0,0));
                            }
                        }else{
                            if(!v[nx][ny][1][tmpMove]){
                                v[nx][ny][1][tmpMove] = true;
                                pq.add(new Node(nx,ny,cur.day,tmpMove,1));
                            }
                        }
                    }
                }
            }
        }

    }

    static int findJump(int x,int y,int dir){
        int idx = 1;

        while(true){
            int nx = x + idx*dx[dir];
            int ny = y + idx*dy[dir];

            if(isOut(nx,ny)){
                break;
            }

            if(board[nx][ny] == 0){
                return idx;
            }

            idx++;
        }

        return -1;
    }

    static boolean isOut(int x,int y){
        if(x < 1 || x > n || y < 1 || y > n)
            return true;
        return false;
    }

    static class Node{
        int x;
        int y;
        int day;
        int move;
        int isDay;

        Node(int x,int y,int day,int move,int isDay){
            this.x = x;
            this.y = y;
            this.day = day;
            this.move = move;
            this.isDay = isDay;
        }
    }
}