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

문제 링크 : https://www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

 

 

이 문제에서 굳이 벽의 위치를 1초마다 변환시키지 않아도, 이미 최초에 저장된 벽의 위치로 탈출 여부를 판단할 수 있다는 것이 키 포인트이다.

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수들을 선언하고 값을 입력받는다. 이 문제는 애초에 8*8 행렬로 고정되어 시작되므로, 동적할당을 하지 않고 전역 변수로 선언해도 메모리를 낭비할 일이 없다.

int y,x,m,ny,nx,my[]={1,1,1,0,0,0,-1,-1,-1},mx[]={-1,0,1,-1,0,1,-1,0,1},nm;
char arr[9][9];
bool ch[9][9][9];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    vector<pair<int,int>> wall;
    for(int i=1; i<=8; i++){
        for(int j=1; j<=8; j++) cin >> arr[i][j];
    }
    queue<pair<pair<int,int>,int>> q;
    q.push({{8,1},0}); // 움직임 횟수
    ch[8][1][0] = true; // 방문 표시
    ...

이때 주의할 점이 ch[9][9][9]로 방문여부를 판단하는 bool문이 설정되었다는 점이다.

ch[y좌표][x좌료][방문횟수]로 해석할 수 있는데, 방문횟수가 최대 8인 이유는 어차피 8초가 지나면 모든 벽들은 사라지기 때문이다.

 

2. 다음은 큐의 while문이다. 아래 코드를 훑어보고 세세하게 이해해보자.

    while(!q.empty()){
        y = q.front().first.first; // 1
        x = q.front().first.second;
        m = q.front().second;
        if(y==1&&x==8){ // 2
            cout << 1 << "\n";
            exit(0);
        }
        q.pop(); // 3
        for(int i=0; i<9; i++){ // 4
            ny = y+my[i];
            nx = x+mx[i];
            nm = min(m+1,8); // 5
            if(ny>=1&&ny<=8&&nx>=1&&nx<=8&&!ch[ny][nx][nm]){
                if(arr[ny-nm+1][nx]=='#') continue; // 이동하고나서 벽이 내려오는지 // 6
                if(arr[ny-nm][nx]=='#') continue; // 이동하려는 위치가 벽인지 // 7
                ch[ny][nx][nm] = true; // 위의 조건들이 아닐 경우 지나갈 수 있는 경로 // 8
                q.push({{ny,nx},nm});
            }
        }
    }
    cout << 0 << "\n"; // 9

(1) 큐의 front에 있는 값들을 변수에 저장한다.

(2) 만약 현재 큐의 값이 (1,8)이라면 미로를 탈출할 수 있다는 뜻이니 1을 출력하고 종료한다.

(3) 큐의 front를 제거해준다.

(4) 0부터 9미만까지 for문을 돌린다. 방향은 십자가향 사방위 + 현재 위치에 stay + 대각선 사방위를 포함하여 모두 9개이다.

(5) 이때 이동횟수의 값은 m+1혹은 8의 최소값이다. 어차피 8을 넘는 순간 모든 장애물들이 사라지므로, 굳이 8을 넘길 필요가 없기 때문이다.

(6) 이 부분은 이동하고나서 벽이 내려오는 위치인지 확인하는 조건문이다. 이럴 경우 곧 바로 다음 for문으로 continue를 해준다.

(7) 이 부분은 이동한 지점이 벽의 위치인지 확인하는 조건문이다. 이럴 경우 곧 바로 다음 for문으로 continue를 해준다.

(8) 만약 6번과 7번을 통과했을 경우, 해당 위치는 이동 가능하다는 의미이므로 방문 표시를 해주고 큐에 삽입해준다.

(9) 큐가 비어서 while문을 종료할 경우, 탈출할 수 없다는 뜻이니 0을 출력한다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int y,x,m,ny,nx,my[]={1,1,1,0,0,0,-1,-1,-1},mx[]={-1,0,1,-1,0,1,-1,0,1},nm;
char arr[9][9];
bool ch[9][9][9];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    vector<pair<int,int>> wall;
    for(int i=1; i<=8; i++){
        for(int j=1; j<=8; j++) cin >> arr[i][j];
    }
    queue<pair<pair<int,int>,int>> q;
    q.push({{8,1},0});
    ch[8][1][0] = true;
    while(!q.empty()){
        y = q.front().first.first;
        x = q.front().first.second;
        m = q.front().second;
        if(y==1&&x==8){
            cout << 1 << "\n";
            exit(0);
        }
        q.pop();
        for(int i=0; i<9; i++){
            ny = y+my[i];
            nx = x+mx[i];
            nm = min(m+1,8);
            if(ny>=1&&ny<=8&&nx>=1&&nx<=8&&!ch[ny][nx][nm]){
                if(arr[ny-nm+1][nx]=='#') continue; // 이동하고나서 벽이 내려오는지
                if(arr[ny-nm][nx]=='#') continue; // 이동하려는 위치가 벽인지
                ch[ny][nx][nm] = true; // 위의 조건들이 아닐 경우 지나갈 수 있는 경로
                q.push({{ny,nx},nm});
            }
        }
    }
    cout << 0 << "\n";
    return 0;
}