[백준] 16954번

16954 움직이는 미로 탈출

문제

---

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

입력

---

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

출력

---

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

(풀이) 

bfs를 이용해서 푼 문제이다. 몇가지만 알아챈다면 쉽게 풀 수 있는 문제였다.

욱제는 1초당 9개의 방향으로 움직일 수 있다는 점, 벽이 없다면 무조건 가장 오른쪽 윗 칸에 도착할 수 있다는 점

벽의 위치가 어딘지가 이 문제의 핵심이므로, 벽의 위치를 임시 저장하는 queue인 wtmp를 만들어 놓고 갱신해주었다.

wall[][]변수는 현재 위치에 벽이 있는지 그 때마다 확인하는 변수이고,

visited[][]변수는 욱제가 이동할 때 겹치는 부분은 삽입하지 않기 위한 변수이다.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
bool visited[8][8];
bool wall[8][8];
queue <pair<int, int>> wtmp;
 
//9개의 방향으로 캐릭터 이동가능.
//왼쪽 상대각선, 상, 오른쪽 상대각선, 좌, 그대로, 우, 왼쪽 하대각선, 하, 오른쪽 하대각선
int dy[9] = { -1,-1,-1,0,0,0,1,1,1 };
int dx[9] = { -1,0,1,-1,0,1,-1,0,1 };
 
int bfs() {
    queue <pair<int, int>> qu;
    qu.push({ 7,0 }); //캐릭터 초기 위치 : 가장 왼쪽 아래 칸
    
    while (!qu.empty())
    {
        int size = qu.size();
        //캐릭터이동
        while (size--)
        {
            int y = qu.front().first;
            int x = qu.front().second;
            qu.pop();
            if (wall[y][x] == true) continue; //벽이 있을경우 더이상 이동 불가
 
            for (int i = 0; i < 9; i++) { //9가지 방향 다 체크
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny >= 0 && ny < 8 && nx >= 0 && nx < 8) {
                    if (wall[ny][nx] == true) continue; //벽이 있을경우 더이상 이동 불가
                    if (ny == 0 && nx == 7) { // 가장 오른쪽 윗 칸으로 갔을 경우
                        return 1;
                    }
                    
                    if (visited[ny][nx] == true) continue; //이미 이전에 방문했던 곳이라면
 
                    visited[ny][nx] = true;
                    qu.push({ ny,nx });
                }
 
            }
        }
 
        //벽이동
        for (int i = 0; i < 8; i++) {
            fill(wall[i], wall[i] + 8, false);
        }
 
        size = wtmp.size();
        for (int i = 0; i < size; i++) {
            int y = wtmp.front().first;
            int x = wtmp.front().second;
            wtmp.pop();
            if (y + 1 >= 8)continue;
            wtmp.push({ y+1,x });
            wall[y + 1][x] = true;
        }
        //시간 절약 방법, 벽이 만약 없다면 가장 오른쪽 로 무조건 갈 수 있으니깐 바로 1을 return 
        if (!qu.empty() && wtmp.size() == 0) return 1;
 
        for (int i = 0; i < 8; i++) {
            fill(visited[i], visited[i] + 8, false);
        }
    }
 
    return 0;
}
 
int main() {
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            char temp;
            scanf("%c", &temp);
            if (temp == '#') {
                wall[i][j] = true;
                wtmp.push({ i,j });
            } 
        }
        getchar(); //개행문자 처리
    }
 
    printf("%d", bfs());
 
    return 0;
}

실행 결과)