[BOJ] 움직이는 미로 탈출 16954번 C++

 

문제

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

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

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

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

입력

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

출력

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

 

접근 방식

 

간단한 BFS문제 같지만 두 가지를 주의해야 한다.

 

1. 제자리에 가만히 있을 수 있다.

2. 벽이 이동할 때, 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터를 이동할 수 없다.

 

처음에는 2차원 방문 배열을 두고

매번 체스판의 상태를 변경시키면서 BFS를 진행했다.

그랬더니 계속 70%쯤에 틀렸습니다.가 나와서 찾아보니

 

3차원 배열로 시간에 따른 방문여부를 확인하면서 풀 수 있음을 알게 되었다.

이때, 매번 새롭게 체스판의 상태를 변경시킬 필요없이

현재 위치에서 시간을 뺀 위치가 벽인지 확인하면 된다.

이때, 현재 그리고 다음 시간에 벽인지 확인 후, 둘 다 벽이 아닐 때 큐에 넣어주면 된다!!

 

또한, 체스판은 8칸 고정이므로

시간이 8초 지난후에는 벽이 모두 사라졌을 것이므로

8초 이후라면 항상 성공할 수 있다~.~

 

 

 

코드

#include<bits/stdc++.h>
using namespace std;
char mat[9][9];
bool visited[9][9][16];
int dr[9][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1},{0,0}};


int main() {
    for(int i=0; i<8; i++) {
        for(int j=0; j<8; j++) {
            cin>>mat[i][j];
        }
    }

    memset(visited, false, sizeof(visited));

    queue<tuple<int,int,int>> q;
    q.push({7,0,0});
    visited[7][0][0] = true;


    while(!q.empty()) {
        int size = q.size();

        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int t = get<2>(q.front());
        q.pop();

        if(x == 0 && y == 7) {
                cout<<1;
                return 0;
        }

        if(t >= 8) { // 모든 벽이 사라졌으므로 성공
            cout<<1;
            return 0;
        }

        int nxt = t+1;
            
        for(int r=0; r<9; r++) {
            int nx = x + dr[r][0];
            int ny = y + dr[r][1];

            if(nx < 0 || ny < 0 || nx >= 8 || ny >= 8) continue;

            bool blocked_now = false;
            if((nx-t) >= 0 && mat[nx-t][ny] == '#') blocked_now = true;

            bool blocked_next = false;
            if((nx-nxt) >= 0 && mat[nx-nxt][ny] == '#') blocked_next = true;

            if(blocked_now || blocked_next) continue;

            if(nxt <= 8 && !visited[nx][ny][nxt]) {
                visited[nx][ny][nxt] = true;
                q.push({nx,ny,nxt});
            }
        }
    }
    cout<<0;
}