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

문제 읽기🤔

---

문제

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

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

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

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

입력

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

출력

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

 

 

문제 풀이📝

---

지문을 잘 읽지 않으면 매우 난처해질 수 있는 문제이다.

욱제는 8방으로 이동할 수 있을 뿐만 아니라 제자리에 서 있을 수도 있다.

고로 통상적인 boolean형의 visited 배열을 사용하여 방문처리를 하게 된다면 제자리에 서 있는 경우를 고려할 수 없게 된다.

그래서 처음에는 방문처리를 하지 않았다.

맵의 크기가 8x8로 고정되어 있기 때문에 중복방문을 수없이 해도 시간초과가 나지 않았지만, 뭔가 찜찜했다.

 

제자리에 서있어야 하는 경우는 다음과 같다.

제자리에 있지 않으면 벽과 겹쳐지기 때문이다.

그러므로 하나의 칸을 팔방으로 이동할 때 한 번, 제자리에서 대기 할 때 한 번, 최대 두 번까지 방문할 수 있기 때문에 visited 배열을 int 형태로 선언하여 두 번을 초과하여 방문한 경우에는 해당 칸을 다시 방문할 수 없도록 했다.

방문처리를 하고 나니 실행 시간이 700ms에서 80ms로 줄어들었다!!!👏

 

 

욱제의 이동과 벽의 이동은 간단하게 구현하였다.

BFS를 수행하기 위해 욱제가 이동한 위치와 그 때의 시간을 Queue에 int형 배열로 담았다.

현재 Queue에서 꺼낸 시간이 이전에 Queue에서 꺼냈던 시간과 다르다면 1초가 지난 것으로 보고 존재하는 모든 벽들을 움직여주었다. (BFS는 너비 우선 탐색이므로 필연적으로 거리(여기서는 시간)가 가까운 곳을 먼저 방문하게 되어 있음)

벽을 움직일 때에는 한 가지 주의할 점이 있는데, 아랫쪽 행에 있는 벽부터 움직여주어야 벽이 겹치는 상황을 피할 수 있다.

 

 

구현🛠️

---

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static char[][] map;
    static int[][] visited;
    static List<Wall> walls;

    static final int[] DX = {-1, 0, 1, 0, 1, 1, -1, -1, 0};
    static final int[] DY = {0, -1, 0, 1, 1, -1, 1, -1, 0};

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

        map = new char[8][8];
        visited = new int[8][8];
        walls = new ArrayList<>();

        for (int i = 0; i < 8; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < 8; j++) {
                if (input[j] == '#'){
                    walls.add(new Wall(i, j));
                }
                map[i][j] = input[j];
            }
        }
        Collections.reverse(walls);
        System.out.println(bfs(7, 0));
    }

    static int bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x, y, 0});
        visited[x][y]++;

        int prevSecond = 0;
        while (!q.isEmpty()) {
            int[] cur = q.poll();

            // 목표 지점에 도달한 경우
            if (cur[0] == 0 && cur[1] == 7){
                return 1;
            }

            // 해당 시간 대의 욱제가 이동할 수 있는 경우를 모두 체크했다면
            // 벽을 움직이고 다음 시간대로 넘어감
            if (prevSecond < cur[2]){
                moveWall();
                prevSecond = cur[2];
            }

            // 현재 벽과 포개어져 있는 상태인지 -> 그렇다면 더 이상 진행 불가
            if (isTrapped(cur)){
                continue;
            }

            for (int d = 0; d < 9; d++){
                int nx = cur[0] + DX[d];
                int ny = cur[1] + DY[d];

                // 방문할 수 없는 경우들
                // 욱제가 제자리에 있기로 선택한 경우, 같은 곳을 한 번 더 방문할 수 있기 때문에 visited 배열을 int 형으로 선언
                // 최대 2번까지만 방문함이 보장되기 때문에, 3번 이상 방문할 경우 그냥 넘어감
                if (isOutOfBound(nx, ny) || map[nx][ny] == '#' || visited[nx][ny] > 2) {
                    continue;
                }
                q.offer(new int[]{nx, ny, cur[2] + 1});
                visited[nx][ny]++;
            }
        }

        return 0;
    }


    static boolean isTrapped(int[] cur){

        if (map[cur[0]][cur[1]] == '#'){
            return true;
        }
        return false;
    }

    static void moveWall(){

        for (Wall wall : walls) {
            wall.move();
        }
    }

    static boolean isOutOfBound(int x, int y){
        if (x < 0 || x >= 8 || y < 0 || y >= 8) {
            return true;
        }
        return false;
    }

    static class Wall {

        int x;
        int y;

        public Wall(int x, int y){
            this.x = x;
            this.y = y;
        }

        public void move(){
            map[x][y] = '.';
            // 범위를 벗어나면 이동할 수 없도록
            if (isOutOfBound(x + 1, y)){
                return;
            }
            x++;
            map[x][y] = '#';
        }
    }
}

 

 

실행결과✅

---