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

문제

BOJ 16954 : https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

접근

이 게임은 시간이 1초 흐를 때마다 벽이 한 칸씩 아래로 내려온다. 캐릭터가 먼저 인접한 빈칸으로 이동한 후 벽이 내려온다. 이때 캐릭터는 이동하지 않고 현재 위치에 서 있을 수도 있다.

 

이 문제의 관건은 시간에 따라 변화하는 미로이다. 따라서 미로를 저장해주는 배열(block)을 3차원으로 선언해 시간의 흐름에 따라 바뀌는 미로의 모양을 저장해 줄 수 있도록 만들었다.

 

나는 BFS로 문제에 접근했다. 이때 큐가 가지고 있을 정보는 좌표(x, y)와 시간(time)이다. 큐에 현재 좌표에서 갈 수 있는 모든 방향을 다시 저장해주면서 가장 오른쪽 위의 좌표까지 도달할 수 있는지 검사해본다. 이때 시간이 지날 때마다 미로의 모양을 바꿔주는 것을 잊지 말자. 또한 이 미로는 8x8이므로 7초 이후에는 모든 벽이 아래로 사라지기 때문에 더이상 벽이 존재하지 않는다. 따라서 8초부터는 더이상 시간을 카운트하지 않아도 된다.

 

코드

// algorithm study
// BOJ_16954_움직이는 미로 탈출

#include <iostream>
#include <queue>
#define endl "\n"
using namespace std;

struct go {
    int x;
    int y;
    int time;
};

int main() {
    char block[10][10][10];
    int visit[10][10][10] = {0};
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            cin >> block[0][i][j];
        }
    }
    queue<go> q;
    q.push({7, 0, 0});
    visit[0][7][0] = 1;
    int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    int chk = 0, count_time = 0;
    while (!q.empty()) {
        go temp;
        temp = q.front();
        q.pop();
        if (temp.time != count_time) {
            count_time = temp.time;
            for (int i = 7; i >= 0; i--) {
                for (int j = 7; j >= 0; j--) {
                    if (i == 0)
                        block[count_time][i][j] = '.';
                    else
                        block[count_time][i][j] = block[count_time - 1][i - 1][j];
                }
            }
        }
        if (block[temp.time][temp.x][temp.y] != '.')
            continue;
        if (temp.x == 0 && temp.y == 7) {
            chk = 1;
            break;
        }
        for (int i = 0; i < 9; i++) {
            int newx = temp.x + dx[i];
            int newy = temp.y + dy[i];

            if (newx < 0 || newx >= 8 || newy < 0 || newy >= 8 || block[temp.time][newx][newy] == '#' || visit[temp.time + 1][newx][newy] == 1)
                continue;
            if (temp.time >= 8)
                temp.time -= 1;
            q.push({newx, newy, temp.time + 1});
            visit[temp.time + 1][newx][newy] = 1;
        }
    }
    if (chk == 0)
        cout << 0;
    else
        cout << 1;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study