Baekjoon 16954번 움직이는 미로 탈출

문제

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

걸린 시간

00 : 20 : 33

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

char board[8][8];
int dy[9] = {-1, 1, 0, 0, 1, 1, -1, -1, 0};
int dx[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

int bfs(){
    queue<pair<int, int>> q;
    q.push(make_pair(7, 0));
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            if(board[y][x] == '#') continue;
            for(int j = 0; j < 9; j++){
                int ny = y+dy[j];
                int nx = x+dx[j];
                if(0 <= ny && ny < 8 && 0 <= nx && nx < 8 && board[ny][nx] != '#'){
                    q.push(make_pair(ny, nx));
                    if(ny == 0 && nx == 7) return 1;
                }
            }
        }
        for(int x = 0; x < 8; x++)
            board[7][x] == '.';
        for(int y = 6; y >= 0; y--){
            for(int x = 0; x < 8; x++){
                if(board[y][x] == '#'){
                    board[y][x] = '.';
                    board[y+1][x] = '#';
                }
            }
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for(int y = 0; y < 8; y++)
        for(int x = 0; x < 8; x++)
            cin >> board[y][x];
    cout << bfs();
    return 0;
}

1초에 한칸씩 욱제가 움직이고 벽을 아래로 이동시켜주는 작업을 bfs 를 통해 구현하면 풀이할 수 있는 쉬운 문제이다.