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

굉장히 시물레이션 느낌이 강한 문제를 풀어보았다. 캐릭터가 가장 왼쪽에서부터 시작해서 가장 오른쪽 윗 칸으로 갈 수 있는지에 대한 여부를 출력하면 되는 문제이다.

문제 자체는 꽤 쉬워보이고 도달할수만 있는거면 그냥 BFS 탐색을 이용해서 장애물 (#) 만 피하면 되지않나 라고 생각할 수 있지만 더 깊은 생각이 필요했다.

먼저 캐릭터는 상하좌우 그리고 대각선 방향으로도 이동이 가능한데 캐릭터가 한번 움직이고 나면은 모든 장애물이 한칸씩 떨어지는 것이다. 그리고 만약 장애물이 떨어진 위치에 사람이 있다면 그 사람은 더 이상 움직이지 못한다. 그리고 장애물이 가장 밑바닥으로 떨어질 경우 삭제된다.

이 구현을 매번 캐릭터가 움직임을 끝낼때 해줘야 했고 그에 따른 일반적인 visited 구현도 바뀔 필요가 있었다. 나는 가장 먼저 이 문제를 보고 예전에 풀었떤 뿌요뿌요 그리고 미네랄 문제가 생각이 났었다. 장애물을 BFS로 따로 유지해야 하지않을까 생각했지만, 미네랄에서는 그 장애물 형태를 유지 해야했기때문에 BFS를 써줬지만 이 문제같은 경우 장애물 좌표만 있으면 됐기에 장애물 좌표 벡터를 따로 관리해주다.

이런식으로 벽돌을 옮겨줬는데 좌표를 유지하면서 가장 밑으로 떨어지는 장애물만 삭제해주었다. 실수 한것이라고는 sort 를 하면은 좌표가 0부터 오름차순으로 나열되는데 가장 밑에있는 좌표부터 해결해야 했어서 index 시작을 끝에서부터 시작했어야했다.

이 구현도 중요했는데, 사람이 벽에 깔리게 되면 그 사람이 들어간 좌표는 계산 안해준다, 왜냐면 움직일 수 없기 때문에. 다만, 장애물은 계속 움직이기 때문에 움직임 후에는 빈칸이 되어서 칸을 업데이트 시켜줘야 했었다. 이걸 생각 못했다면 더 오랜 시간이 걸렸을수도 있었다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

char matrix[8][8]; 
bool visited_person[8][8]; 
vector<pair<int,int>> wallVec;
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}}; 

struct Person{
    int x, y; 
};

void Input(){
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            char c;
            cin >> c; 
            if(c == '#') wallVec.push_back({i,j}); 
            matrix[i][j] = c; 
        }
    }
}


void Solution(){
    int answer = 0; 
    memset(visited_person,false,sizeof(visited_person)); 
    queue<Person> q;
    q.push({7,0}); 
    visited_person[7][0] = true; 
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            Person person = q.front();
            q.pop(); 

            int x = person.x, y = person.y; 
            
            //사람이 벽에 깔렸다 -> 움직이지 못한다 
            if(matrix[x][y] == '#'){
                visited_person[x][y] = false; 
                continue; 
            }

            if(x == 0 && y == 7){
                cout << 1;
                return; 
            }

            //사람 움직이기 
            for(pair<int,int>& p : dir){
                int nX = x + p.first;
                int nY = y + p.second; 

                if(nX < 0 || nY < 0 || nX >= 8 || nY >= 8 || matrix[nX][nY] == '#' || visited_person[nX][nY]) continue; 

                
                q.push({nX,nY}); 
                visited_person[nX][nY] = true; 
            }

            //제자리에 있을수도 있다
            q.push({x,y}); 
            visited_person[x][y] = true; 

        }
        //벽돌 움직이기 
        if(!wallVec.empty()){
            sort(wallVec.begin(),wallVec.end()); 
            vector<pair<int,int>> newWall; 
            for(int j = wallVec.size()-1; j >= 0; j--){
                //cout << wallVec[j].first << ' ' << wallVec[j].second << endl; 
                int nX = wallVec[j].first + 1; 
                int nY = wallVec[j].second + 0; 

                if(nX >= 8){
                    matrix[wallVec[j].first][wallVec[j].second] = '.'; 
                    wallVec.erase(wallVec.begin() + j); 
                    //j++; 
                    continue; 
                }
                
                matrix[wallVec[j].first][wallVec[j].second] = '.'; 
                matrix[nX][nY] = '#'; 
                newWall.push_back({nX,nY}); 
            }
            wallVec = newWall; 
        } 
    }

    cout << answer; 

}

// void test(){
//     vector<pair<int,int>> v = {{7,0},{7,2},{6,3},{2,3}}; 
//     sort(v.begin(),v.end());  
//     for(int i = v.size()-1; i >= 0; i--){
//         cout << v[i].first << ' ' << v[i].second << endl; 
//     }
// }


void Solve(){
    Input();
    Solution(); 
    //test(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

추가적으로 test() 함수를 만들어서 자잘구리한것들을 확인 할 수 있는 아이디어를 생각했다. 되게 좋은 생각 같다.

배운점:
1. 좌표 방문 벡터의 중요성
2. 장애물 움직이기