[백준] 13460 - 구슬탈출(2) by C++

너비우선탐색(bfs)를 활용한 문제이다.

핵심은 너비우선탐색을 진행할때 상,하,좌,우를 한 칸씩 진행하는 것이 아닌
판을 기울이는 것이기 때문에 4가지 방향에 대해서 구슬이 끝까지 움직했을 때로 bfs진행해야한다.
빨간구슬과 파란구슬의 위치를 고려하지 않고 벽이 나올때 까지 움직인다.
빨간구슬과 파란구슬의 위치가 같으면 > 더 많이 움직인 애가 뒤에 위치하도록 한다.
하나의 방향으로 움직임이 모두 끝났을 때, 빨간색 구슬만 구멍에 들어간 경우 count한 횟수 리턴.
빨간색 구슬과 파란색 구슬이 모두 구멍에 안들어간 경우에만 큐에 넣는다.
10회가 "초과"되었을 때, 무조건 -1이 리턴되도록 한다.

❗️메모리초과

위의 알고리즘으로 구현했을 때 메모리초과가 떴다.
매 bfs함수에서 4가지 방향 모두를 큐에 넣으면 메모리 초과발생.
상,하로 움직인 경우에는 좌,우의 움직임만 계산하고
좌,우로 움직인 경우에는 상,하의 움직임만 계산

💻 C++ 코드

/*
<핵심>
상,하,좌,우 끝까지 움직임의 결과를 큐에 넣은 bfs
*/ 

#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>

using namespace std;
typedef struct STATUS{
    int rx,ry;
    int bx,by;
    bool rMeetO;
    bool bMeetO;
    int pastdir;
    int count;
}Status;
char board[10][10];
int ox,oy;
int mx[4] = {0,0,1,-1};
int my[4] = {1,-1,0,0};


int bfs(queue<Status> q){
    // get direction from queue
    if(q.empty()){
        return -1;
    }

    Status cur_st = q.front();
    Status nxt_st;
    q.pop();
    if(cur_st.count > 10){
        return -1;
    }
    // move while red boll meet the wall
    for(int dir = 0; dir < 4 ; dir++){
        // cout << "dir=" << dir << "\n";
        if(dir/2 != cur_st.pastdir/2){
            nxt_st = cur_st;
            nxt_st.pastdir = dir;
            nxt_st.count = cur_st.count+1;
            if(nxt_st.count > 10) return -1;
            while(board[nxt_st.rx + mx[dir]][nxt_st.ry+my[dir]] != '#' || board[nxt_st.bx + mx[dir]][nxt_st.by+my[dir]]!='#'){
                if(board[nxt_st.rx + mx[dir]][nxt_st.ry+my[dir]] != '#'){
                    nxt_st.rx += mx[dir];
                    nxt_st.ry += my[dir];
                    if(nxt_st.rx == ox && nxt_st.ry == oy){
                        nxt_st.rMeetO = true;
                    }
                }
                if(board[nxt_st.bx + mx[dir]][nxt_st.by+my[dir]]!='#'){
                    nxt_st.bx += mx[dir];
                    nxt_st.by += my[dir];
                    if(nxt_st.bx == ox && nxt_st.by ==oy){
                        nxt_st.bMeetO = true;
                    } 
                }
            }
            // if Red and Blue are in the same position, the one whoes movement is far places behind the other one.
            if(nxt_st.rx == nxt_st.bx && nxt_st.ry == nxt_st.by){
                if(abs(nxt_st.rx - cur_st.rx + nxt_st.ry - cur_st.ry) > abs(nxt_st.bx - cur_st.bx + nxt_st.by - cur_st.by)){
                    nxt_st.rx -= mx[dir];
                    nxt_st.ry -= my[dir];
                } else{
                    nxt_st.bx -= mx[dir];
                    nxt_st.by -= my[dir];
                }
            }
            
            if(nxt_st.rMeetO && !nxt_st.bMeetO){
                return nxt_st.count;
            } 
            else if(!nxt_st.rMeetO && !nxt_st.bMeetO){
                if(nxt_st.rx != cur_st.rx || nxt_st.ry != cur_st.ry || nxt_st.bx != cur_st.bx || nxt_st.by != cur_st.by){
                    q.push(nxt_st);
                }
            } 

        }
        
    }

    return bfs(q);
}

int main(){
    int n,m;
    cin >> n >> m;
    Status st;
    queue<Status> q;
    st.count = 0;
    st.rMeetO = false;
    st.bMeetO = false;
    st.pastdir = 5;
    for(int i=0; i<n;i++){
        for(int j=0;j<m;j++){
            // int tmp;
            cin >> board[i][j];
            if(board[i][j]=='R'){
                st.rx = i;
                st.ry = j;
            } else if(board[i][j]=='B'){
                st.bx = i;
                st.by = j;
            } else if(board[i][j]=='O'){
                ox=i;
                oy=j;
            }
        }
    }
    q.push(st);
    // only one bfs => answer
    cout << bfs(q);
    return 0;
}