[백준][C++] 13459 구슬 탈출

www.acmicpc.net/problem/13459

13459번: 구슬 탈출

 

 

 

알고리즘 종류

    - 구현

 

 

사고 과정

    1. 구슬의 이동은 BFS로 처리한다.

    2. 이동 중에 출구('O')를 만나면, flag에 기록했다가 처리한다.

    3. 이동 중에 벽('#')을 만나면, 멈춘다.

    4. 이동 후에 빨간 공과 파란 공의 위치가 같으면, 위치를 재조정한다.

        - 옮기기 전에, 어떤 공이 뒤에 있었는지 확인하여, 옮긴다.

    5. queue에 두 공에 대한 정보를 넣고 다시 BFS를 수행한다.

 

 

 

구현(C++)

#include <iostream>
#include <queue>
 
using namespace std;
 
struct Ball{
    int y, x;
};
 
Ball R, B;
 
int n, m;
bool flag = false;
 
char mat[11][11];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
void solution(){
    
    queue<pair<Ball, Ball> > q;
    q.push({R, B});
    int cnt = 1;
    
    while(!q.empty()){
        int size = q.size();
        if(cnt == 11) break;
        
        for(int i=0; i<size; i++){
            
            int ry = q.front().first.y;
            int rx = q.front().first.x;
            int by = q.front().second.y;
            int bx = q.front().second.x;
            
            q.pop();
            
            for(int d=0; d<4; d++){
                int rny = ry, rnx = rx;
                int bny = by, bnx = bx;
                bool rf=false, bf=false;
                
                // Red
                while(true){
                    rny += dir[d][0];
                    rnx += dir[d][1];
                    if(mat[rny][rnx] == 'O'){
                        rf = true;
                        break;
                    }
                    
                    if(mat[rny][rnx] == '#'){
                        rny -= dir[d][0];
                        rnx -= dir[d][1];
                        break;
                    }
                }
                
                // Blue
                while(true){
                    bny += dir[d][0];
                    bnx += dir[d][1];
                    if(mat[bny][bnx] == 'O'){
                        bf = true;
                        break;
                    }
                    if(mat[bny][bnx] == '#'){
                        bny -= dir[d][0];
                        bnx -= dir[d][1];
                        break;
                    }
                }
            
                if(bf) continue;
                if(rf) {
                    cout << 1 << endl;
                    return;
                }
                
                // 옮겼는데 같은 위치일 경우  
                if(rny == bny && rnx == bnx){
                    if(d==0){
                        if(ry < by) rny -= 1;
                        else bny -= 1;
                    }
                    else if(d==1){
                        if(rx < bx) rnx -= 1;
                        else bnx -= 1;
                    }
                    else if(d==2){
                        if(ry > by) rny += 1;
                        else bny += 1;
                    }
                    else if(d==3){
                        if(rx > bx) rnx += 1;
                        else bnx += 1;
                    }
                }
 
                Ball rb, bb;
                rb.y = rny;
                rb.x = rnx;
                
                bb.y = bny;
                bb.x = bnx;
                q.push({rb, bb});
            }
        }
        cnt++;
    }
    cout << 0 << endl;
}
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> mat[i][j];
            if(mat[i][j] == 'B'){
                B.y = i;
                B.x = j;
                mat[i][j] = '.';
            }
            else if(mat[i][j] == 'R') {
                R.y = i;
                R.x = j;
                mat[i][j] = '.';
            }
        }
    }
    
    solution();
}
 

 

 

 

시행착오

    - 오랜만에 풀어보는 구현 문제여서 풀이하는데 꽤 오래걸렸다. 이 문제에서 깨달은 것만 3가지나 된다. 앞으로 구현 문제의 유형을 정리하면서 풀이 방법을 기록해야겠다.