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

문제 링크

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

풀이 과정

map = new char[SIZE][SIZE][SIZE];
moveWall();

맵은 8X8 크기로, 벽이 1초마다 내려온다는 조건에 따라 8초 이후부터는 체스판 상에 벽이 존재하지 않음을 파악할 수 있습니다. 이를 토대로 배열을 3차원으로 설정해주었으며, z 축은 0~7초 순간의 체스판 모양을 기억합니다. 이후 moveWall 메소드를 호출해, 1~7초 때의 체스판 모양을 설정해줍니다.

static void moveWall() {
    for (int sec = 1; sec < SIZE; sec++) {
        for (int j = 0; j < SIZE; j++) {
            for (int i = SIZE - 2; i >= 0; i--) {
                map[i + 1][j][sec] = map[i][j][sec - 1];
            }
            map[0][j][sec] = '.';
        }
    }
}

moveWall 메소드는 1초 전의 체스판 형태를 한 칸 내려 현재 초에 저장합니다.

while (!queue.isEmpty()) {
    Point now = queue.poll();

    if (map[now.x][now.y][now.second >= SIZE ? SIZE - 1 : now.second] == '#') continue;

    if (check(now.x, now.y, now.second) || (now.x == 0 && now.y == SIZE - 1)) {
        reach = true;
        break;
    }

    if (now.second + 1 >= SIZE || map[now.x][now.y][now.second + 1] != '#')
        queue.add(new Point(now.x, now.y, now.second + 1));

    for (int d = 0; d < 8; d++) {
        int nx = now.x + dx[d];
        int ny = now.y + dy[d];

        if (!inRange(ny, nx) || map[nx][ny][now.second >= SIZE ? SIZE - 1 : now.second] == '#') continue;

        queue.add(new Point(nx, ny, now.second + 1));
    }
}

이후에는 이동 가능한 8 방향 및 이동하지 않는 선택까지 포함해서 총 9가지 경우에 대해, 다음 초, 다음 위치에 벽이 존재하지 않으면, 큐에 넣어주며 bfs 탐색을 진행합니다.

if (check(now.x, now.y, now.second) || (now.x == 0 && now.y == SIZE - 1)) {
    reach = true;
    break;
}

위 코드와 같은 가지치기를 해주지 않으면, 큐에 너무 많은 정보가 들어가기 때문에 메모리 초과가 발생하게 됩니다. 위 코드는, 큐에서 꺼낸 현재 좌표를 토대로 더이상 진행하지 않고도 목적지에 도달할 수 있는지를 확인하는 코드입니다. check 메소드의 결과와 현재 좌표가 목적지 좌표와 같다면 도달할 수 있음을 boolean 변수에 저장해줍니다.

static boolean check(int x, int y, int sec) {
    if (x == 0) return true;
    for (int i = x - 1; i >= 0; i--)
        if (map[i][y][sec] == '#') return false;

    return true;
}

더이상의 큐에 넣고 빼는 작업 없이도 목적지에 도달함을 확인할 수 있는 방법은 다음과 같습니다.

1. 현재 체스판의 맨 윗줄에 위치하는 경우.
2. 현재 좌표를 기준으로 위에 벽이 하나도 없는 경우.

1의 경우, 다음 초부터는 오른쪽에 벽이 존재할 수 없기 때문에 이동할 수 있습니다. 2의 경우는 위에 벽이 없기 때문에, 위로만 이동한 뒤 1과 같이 이동할 수 있습니다.

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static final int SIZE = 8;
    static char[][][] map;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

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

        map = new char[SIZE][SIZE][SIZE];

        for (int i = 0; i < SIZE; i++) {
            String s = sc.next();
            for (int j = 0; j < SIZE; j++) {
                map[i][j][0] = s.charAt(j);
            }
        }

        moveWall();

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(7, 0, 0));
        boolean reach = false;

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            if (map[now.x][now.y][now.second >= SIZE ? SIZE - 1 : now.second] == '#') continue;

            if (check(now.x, now.y, now.second) || (now.x == 0 && now.y == SIZE - 1)) {
                reach = true;
                break;
            }

            if (now.second + 1 >= SIZE || map[now.x][now.y][now.second + 1] != '#')
                queue.add(new Point(now.x, now.y, now.second + 1));

            for (int d = 0; d < 8; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];

                if (!inRange(ny, nx) || map[nx][ny][now.second >= SIZE ? SIZE - 1 : now.second] == '#') continue;

                queue.add(new Point(nx, ny, now.second + 1));
            }
        }

        System.out.println(reach ? 1 : 0);
    }

    static boolean check(int x, int y, int sec) {
        if (x == 0) return true;
        for (int i = x - 1; i >= 0; i--)
            if (map[i][y][sec] == '#') return false;

        return true;
    }

    static void moveWall() {
        for (int sec = 1; sec < SIZE; sec++) {
            for (int j = 0; j < SIZE; j++) {
                for (int i = SIZE - 2; i >= 0; i--) {
                    map[i + 1][j][sec] = map[i][j][sec - 1];
                }
                map[0][j][sec] = '.';
            }
        }
    }

    static boolean inRange(int y, int x) {
        if (x < 0 || x > 7 || y < 0 || y > 7) return false;
        return true;
    }

    static class Point {
        int x, y, second;

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