(C++) - 백준(BOJ) 16954번 : 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

bfs문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

string 배열 chess에 체스판을 입력받습니다. 9방향 (상, 하, 좌, 우, 대각선 4방향, 가만히 있기)를 살펴보기 위한 일차원 배열 dr, dc를 선언합니다.

 

📔 풀이과정

 고정된 미로를 탐색하는 bfs방식이 아닌 벽이 한 줄씩 내려오는 특성이 있습니다. 따라서 brute force방식으로 편하게 모든 경우의 수를 탐색하고 싶으나 재귀 방식으로 구현할 경우에는 매 이동마다 9개 경우가 생기므로 (7행 0열)에서 출발해 9씩 곱한다면 81칸이 있는 곳으로 9가지로 이동한다면 적절히 pruning하지 않는 이상 시간초과가 날 것입니다. 따라서 bfs를 적절히 수행하도록 구현해야 합니다.

 

 1. q에 시작점 7행, 0열을 push하고 bfs는 시작됩니다.

 

 2. 매 q의 size만큼 while loop를 도는데 이것이 곧 1초동안 움직일 수 있는 움직임의 상태들 전부입니다. 이 qsize동안 각 좌표에서 이동할 수 있는 9가지의 경우의 수를 따져 q에 push합니다. 이동할 수 있는 경우는 다음칸이 유효(다음 칸이 chess판 안에 있다), 다음칸에 장애물이 없으며, 다음칸의 위칸또한 장애물이 없어야(다음 초에 장애물이 내려오기 때문에 움직이기 전에 게임이 끝납니다. ) 합니다.

 

 3. 1초 동안 움직임을 모두 push했으니 chess의 벽을 모두 한 칸씩 내려줍니다.

 

 4. 0행에 도착했다면 무조건 0행 7열은 도착할 수 있습니다. 0행에 도착한 시점에는 이 행에 벽이 있을 수 없기 때문입니다. 따라서 bfs함수를 종료 후 1을 반환해줍니다. 모든 유효한 이동을 시도했음에도 0번째 행에 도착할 수 없었다면 0을 반환합니다.

 

📔 정답출력

 bfs의 결과값을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using tpi = tuple<int,int>;
string chess[8];
int dr[] = {0,0,1,-1,-1,-1,1,1,0};
int dc[] = {1,-1,0,0,-1,1,-1,1,0};

void moveChess(){
    for(int i = 7; i >= 1; i--)
        chess[i] = chess[i-1];
    chess[0] = "........";
}

int bfs(){
    queue<tpi> q;
    q.push({7,0});
    while(!q.empty()){
        int qSize = q.size();

        while(qSize--){
            int r,c;
            tie(r,c) = q.front();
            q.pop();
            
            if(r == 0) return 1;

            for(int i = 0; i < 9; i++){
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(0 > nr || nr >= 8 || 0 > nc || nc >= 8) continue;
                if(chess[nr][nc] == '#') continue;
                if(nr - 1 >= 0 && chess[nr - 1][nc] == '#') continue;
                q.push({nr,nc});
            } 
        }
        moveChess();
    }
    return 0;
}

int main(){
    for(int i = 0; i < 8; i++) cin >> chess[i];
    cout << bfs();
}

---

📕 Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

.#######
..######
#.......
.#######
........
#.......
.#######
........

답 : 1

 

input

........
..######
#.......
.#######
........
#.......
.#######
........

답 : 1