백준 134760 구슬 탈출 2 C++

간단한 해설

 

백준 16197 두 동전 C++

 

이전에 풀었던 두 동전 문제와 유사하게 풀이할 수 있다.

 

일단 유형은 bfs+구현(시뮬)의 느낌이다.

 

hash맵인 unordered_map을 이용하여 방문 여부를 O(1)의 시간복잡도로 확인하고,

 

기울여서 구슬을 넣어보면 된다.

 

기울였을 때, 구슬 2개가 동시에 들어가면 실패인데, 이 테스트 케이스를 잘 확인해봐야 한다.

 

기울이는 것을 어떻게 구현할까 고민했는데, 경우의 수가 4가지이므로 그냥 if 분기 여러 개로 처리하였다.

 

move 함수를 잘구현하여서 오히려 코드 가독성이 좋아졌다.

 

혹시 모르는 사람을 위해서 참고로 설명하자면 &는 참조자인데, 이를 활용해서 board를 call by ref로 호출할 수 있다. 

답

 

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
int n,m;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
pair<int,int> endHole;

string boardToString(vector<string>& board){
    string retStr="";
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            retStr+=board[i][j];
        }
    }
    return retStr;
}
bool canMove(vector<string>& board,pair<int,int> order){
    if(order.first<0||order.first>n||order.second<0||order.second>=m) return false;
    if(board[order.first][order.second]=='#') return false;
    if(board[order.first][order.second]=='B') return false;
    if(board[order.first][order.second]=='R') return false;
    return true;

}

void move(vector<string>& board,pair<int,int> order,int direction,bool isRed){
    if(board.size()==1) return;

    pair<int,int> crnOrder=order;

    bool flag=false;
    char sig=isRed?'R':'B';

    while(true){
        pair<int,int> nxtOrder={
            crnOrder.first+dy[direction],
            crnOrder.second+dx[direction]
        };
        if(canMove(board,nxtOrder)){
            if(board[nxtOrder.first][nxtOrder.second]=='O'){
                board[crnOrder.first][crnOrder.second]='.';
                break;
            }
            else{
                board[nxtOrder.first][nxtOrder.second]=sig;
                board[crnOrder.first][crnOrder.second]='.';
                crnOrder=nxtOrder;
            }
        }
        else break;
    }
    return;
}



vector<string> moveBoard(vector<string>& prevboard,pair<int,int> prevRedOrder,pair<int,int> prevBlueOrder,int direction){
    vector<string> nxtBoard=prevboard;
    if(direction==0){
        if(prevRedOrder.first<prevBlueOrder.first){
            move(nxtBoard,prevRedOrder,direction,true);
            move(nxtBoard,prevBlueOrder,direction,false);
        }
        else{
            move(nxtBoard,prevBlueOrder,direction,false);  
            move(nxtBoard,prevRedOrder,direction,true);
        }
    }
    else if(direction==1){
        if(prevRedOrder.first<prevBlueOrder.first){
            move(nxtBoard,prevBlueOrder,direction,false);
            move(nxtBoard,prevRedOrder,direction,true);
        }
        else{
            move(nxtBoard,prevRedOrder,direction,true);
            move(nxtBoard,prevBlueOrder,direction,false);
        }
    }
    else if(direction==2){
        if(prevRedOrder.second<prevBlueOrder.second){
            move(nxtBoard,prevRedOrder,direction,true);
            move(nxtBoard,prevBlueOrder,direction,false);
        }
        else{
            move(nxtBoard,prevBlueOrder,direction,false);
            move(nxtBoard,prevRedOrder,direction,true);
        }
    }
    else{
        if(prevRedOrder.second<prevBlueOrder.second){
            move(nxtBoard,prevBlueOrder,direction,false);
            move(nxtBoard,prevRedOrder,direction,true);
        }
        else{
            move(nxtBoard,prevRedOrder,direction,true);
            move(nxtBoard,prevBlueOrder,direction,false);
        }
    }
    bool isRedExist=false;
    bool isBLueExist=false;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(nxtBoard[i][j]=='R') isRedExist=true;
            else if(nxtBoard[i][j]=='B') isBLueExist=true;
        }
    }
    if(!isRedExist&&!isBLueExist){
        nxtBoard=vector<string>(1,"fail");
    }
    else if(!isRedExist||!isBLueExist){
        if(!isRedExist){
            nxtBoard=vector<string>(1,"success");
        }
        else nxtBoard=vector<string>(1,"fail");
    }
    return nxtBoard;
}


int main(){
    cin>>n>>m;
    vector<string> v(n);
    
    pair<int,int> redPoint;
    pair<int,int> bluePoint;

    for(int i=0;i<n;++i){
        cin>>v[i];
        for(int j=0;j<m;++j){
            if(v[i][j]=='R'){
                redPoint={i,j};
            }
            else if(v[i][j]=='B'){
                bluePoint={i,j};
            }
            else if(v[i][j]=='O'){
                endHole={i,j};
            }
        }
    }

    unordered_map<string,int> visited;
    priority_queue<tuple<int,vector<string>,pair<pair<int,int>,pair<int,int>>>> q;
    
    string thisIsFirstBoard=boardToString(v);
    visited[thisIsFirstBoard]=0;
    q.push({0,v,{redPoint,bluePoint}});
    int ans=-1;
    while(!q.empty()){
        int crnTime=-get<0>(q.top());
        vector<string> crnBoard=get<1>(q.top());
        pair<int,int> crnRedPoint=get<2>(q.top()).first;
        pair<int,int> crnBluePoint=get<2>(q.top()).second;
        q.pop();

        if(crnTime>=10) break;

        bool flag=false;
        for(int i=0;i<4;++i){
            vector<string> nxtBoard=moveBoard(crnBoard,crnRedPoint,crnBluePoint,i);

            if(nxtBoard.size()==1){
                if(nxtBoard[0]=="fail") continue;
                if(nxtBoard[0]=="success"){
                    flag=true;
                    ans=crnTime+1;
                    break;
                }
            }
            string nxtBoardString=boardToString(nxtBoard);
            if(visited.find(nxtBoardString)==visited.end()){
                visited[nxtBoardString]=crnTime+1;
                pair<int,int> nxtRedPoint;
                pair<int,int> nxtBluePoint;
                for(int i=0;i<n;++i){
                    for(int j=0;j<m;++j){
                        if(nxtBoard[i][j]=='R'){
                            nxtRedPoint={i,j};
                        }
                        else if(nxtBoard[i][j]=='B'){
                            nxtBluePoint={i,j};
                        }
                    }
                }
                q.push({-(crnTime+1),nxtBoard,{nxtRedPoint,nxtBluePoint}});
            }
        }
        if(flag) break;
    }
    cout<<ans;
}