[백준/C++] 16954 움직이는 미로탈출

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

16954번: 움직이는 미로 탈출

이 문제는 bfs 기본코드에서 약간의 응용이 필요하다.

우선 갈 수 있는 방향이 1.상 2.하 3.좌 4.우 5.좌상 6.우상 7.좌하 8.우하 9.제자리 로 총 9가지다.

​

그리고 벽이 1초에 한 줄씩 내려온다고 하였으므로, 1초마다 벽의 위치를 움직여줘야한다.

0,0에서 부터 for문을 시작하면 벽을 내리고, 내린 벽과 기존 벽을 구분하기 어려우므로

밑에서부터 for문을 시작하여 윗 줄에 벽이 있다면 아래로 내려주는 식으로 진행한다.

그리고 맨 윗줄은 1초라도 경과하면 벽이 존재할 수 없으므로 빈칸으로 채워준다.

-> 이 코드는 굳이 매초마다 보드의 상태를 바꿀 때 쓸 필요없이, 딱 한번만 실행되도 상관없다!

​

매초마다 너비우선탐색을 진행하고 나면, 방문을 기록한 배열을 초기화해준다!

이유는, 벽을 피하기 위해서는 이전에 방문했던 곳으로 피할 수도 있기 때문에 bfs탐색 시에만 무한 루프를 방지하기 위해 방문했던 곳을 기록하고 한 좌표에 대한 bfs가 끝나면 그 좌표와 연관된 좌표의 방문 기록은 초기화 해준다.

​

큐의 사이즈를 이용하여 탐색을 진행하는 이유?

-> 1초마다 한번 이동 하고, 벽이 내려온다. 매초마다 이동 가능한 좌표들에 대해 전부 탐색해줘야하기 때문이다.

처음엔 왼쪽 하단에서 bfs를 진행하여 이동 가능한 좌표들을 전부 큐에 넣고

빨간색 세모는 시작점에서 이동 가능한 좌표들

1초 경과 후에는 앞서 넣었던 좌표들에 대해 bfs를 진행하여 해당 좌표에서 이동 가능한 좌표들을 전부 큐에 넣고,

파란색 체크표시는 빨간색 세모에서부터 이동가능한 좌표들

​

2초 경과 후에는 앞서 넣었던 좌표들에 대해 bfs를 진행하여 해당 좌표에서 이동 가능한 좌표들을 전부 큐에 넣는 식으로 반복하기 위해서 큐의 사이즈를 활용한다!

핑크색 동그라미는 파란색 체크표시에서 이동 가능한 좌표들

(해당 시간에서 이동 가능한 좌표들의 수 = 큐의 사이즈)

= 그래서 큐의 사이즈가 시간 단위가 되는 것이다!

​

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <cstring>

using namespace std;

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

char board[8][8];
int visited[8][8];
queue<pair<int,int>> q;

bool outofindex (int a, int b){
    return (a < 0 || a >=8 || b < 0 || b>=8);
}

void resetboard(){
    for(int i=6; i>=0;i--) {
        for (int j = 0; j < 8; j++) {
            board[i+1][j]=board[i][j];
        }
    }
    for(int i=0; i < 8; i++) board[0][i] = '.';
}

int bfs(){
    while(!q.empty()) {
        memset(visited,0, sizeof(visited));
        int size = q.size(); // 시간 단위로 수행
        while(size--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if(board[x][y] == '#') continue;

            for(int i=0; i<9; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx==0 && ny == 7) return 1;
                if(outofindex(nx,ny) || board[nx][ny]=='#' || visited[nx][ny]){
                    continue;
                }
                q.push({nx,ny});
                visited[nx][ny]=true;
            }
        }
        resetboard();
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    pair<int,int> starting = {7,0};

    for(int i=0; i<8;i++){
        for(int j=0; j<8; j++){
            cin >> board[i][j];
        }
    }
    q.push(starting);
    visited[starting.first][starting.second]=true;
    cout << bfs();

    return 0;
}