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

www.acmicpc.net/problem/16954

16954번: 움직이는 미로 탈출

 

 

 

알고리즘 종류

 

 

 

사고 과정

    1. 욱제를 9방향으로 움직인다.

    2. 벽을 내린다.

    

    - 고려해야할 상황은, 욱제가 벽을 피하기 위해서 이전 시간대에 갔던 위치를 다시 갈 수 있다. 따라서 방문을 체크하는 배열을 시간대에 따라 초기화해야 한다.

 

 

 

구현(C++)

#include <iostream> 
#include <cstring>
#include <queue>
 
using namespace std;
 
char mat[9][9];
int isVisited[9][9];
int dir[9][2] = {{0,0}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0}, {-1,-1}, {0,-1},{1,-1}};
 
 
bool isValid(int y, int x){
    return (y>=1 && y<=8) && (x>=1 && x<=8);
}
 
 
// 벽 내리기  
void down_walls(){
    for(int i=7; i>=0; i--){
        for(int j=1; j<=8; j++){
            mat[i+1][j] = mat[i][j];
        }
    }
}
 
 
bool bfs(){
    
    queue<pair<int, int> > q;
    q.push({8,1});
    isVisited[8][1] = 1;
    
    while(!q.empty()){
        memset(isVisited,0, sizeof(isVisited)); // 벽을 피하기 위해서 이전에 갔던 자리를 다시 방문할 수 있다. 
        int size = q.size(); // 시간 단위로 수행  
        
        while(size--){
            int cy = q.front().first;
            int cx = q.front().second;
            q.pop();
            
            if(mat[cy][cx] == '#') continue; // 욱제가 이동한 자리에 벽이 온 경우  
            
            for(int d=0; d<9; d++){
                int ny = cy + dir[d][0];
                int nx = cx + dir[d][1];
                
                if(ny==1 && nx==8) return true; // 목적지 도착  
                
                if(!isValid(ny, nx)) continue;
                if(mat[ny][nx] == '#') continue;
                if(isVisited[ny][nx]) continue;
                
                isVisited[ny][nx] = 1;
                q.push({ny, nx});
            }
        }
        
        down_walls();
    }
    
    return false;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    for(int i=1; i<=8; i++){
        for(int j=1; j<=8; j++){
            cin >> mat[i][j];
        }
    }
    for(int j=1; j<=8; j++) mat[0][j] = '.';
    
    if(bfs()) cout << 1 << endl;
    else cout << 0 << endl;
}
 

 

 

 

시행착오

    - 시간대마다 방문을 체크하는 배열(isVisited)를 초기화 하지 못했서 제출이 안됬다. 왜인지 이전에 갔던 곳을 재방문할 수 있다고 생각은 해놓고 막상 구현은 하지 않은 나의 멍청함이 시간을 잡아먹었다. 시도해봤어야 했는데... 왜 그랬을까? 반성하고 다음에는 시도하자...!