BOJ 16954 움직이는 미로 탈출

 

BOJ 백준 16954 C++

움직이는 미로탈출 

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

 

 

1) BFS - 완전히 전형적으로 나오는 BFS에서 조금 더 생각해야 함. 이와 유사 문제가 많음. 당장 생각나는 문제는 삼성 기출의 구슬 문제.

2) 몇 달 전에는 많이 헤맸던 유형인데 이제는 예전보다 풀만하다. 정답 제출하고 다른 풀이도 몇 개 봤는데 세부적인 구현이 갈리는 것 같다.

나는 단계별로 맵을 움직이기 위해 반복문(while)을 두 개 사용해서 구현했다.

3) 처음에 문제에서 [ 욱제 이동->벽 이동 ] 이라고 해서 욱제의 위치를 움직이고 벽을 이동하는 쪽으로 구현할까? 했는데,

그보다는 벽을 '먼저' 움직여놓고(line 40), 벽과 겹치지 않는 욱제의 위치(line 68)를 큐에 담았다.

 

이때 시작점에서 예외가 생길 수 있어서 시작점에 관한 코드를 추가했다(line 23) --> tc 4참고

 

 

 

/**
 * 200905
 * BOJ 16954 움직이는 미로 탈출
 * BFS
 * */

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int N=8;
char map[9][9];
bool check[9][9];
int dx[8]={0,0,1,1,1,-1,-1,-1};
int dy[8]={-1,1,1,-1,0,1,-1,0};

bool exitFlag=true;

void solveBFS(){
    queue <pair<int,int> > q;
    q.push(make_pair(7,0));
    for(int i=0; i<8; i++){
        int nx = 7 + dx[i];
        int ny = 0 + dy[i];

        if(0<=nx && nx<N && 0<=ny && ny<N){
            if(map[nx][ny]=='.') q.push(make_pair(nx,ny));
        }
    }

    while(1){
        if(q.empty()) {
            exitFlag=false; break;
        }
        memset(check, 0, sizeof(check));
        int q_size = q.size();

        // <-- map move start -->
        char nmap[9][9];
        for(int i=N; i>1; i--)
            for(int j=0; j<N; j++)
                nmap[i-1][j] = map[i-2][j]; 
        for(int i=0; i<N; i++)
            nmap[0][i] = '.';

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                map[i][j] = nmap[i][j];
        // <-- map move end -->

        while(q_size--){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if(map[x][y]=='#') continue;
            
            if(x==0 && y==N-1) {
                return;
            }

            for(int i=0; i<8; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(0<=nx && nx<N && 0<=ny && ny<N){
                    if(!check[nx][ny] && map[nx][ny]=='.'){
                        q.push(make_pair(nx,ny));
                        check[nx][ny] = true;
                    }
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    for(int i=0; i<N; i++)
        cin >> map[i];
    
    solveBFS();

    if(!exitFlag) cout << 0;
    else cout << 1;

    return 0;
}