[BOJ/백준][Gold4] 13459 : 구슬 탈출 (C++)

 

www.acmicpc.net/problem/13459

13459번: 구슬 탈출

 

[난이도] Gold4

[유형] BFS (삼성SW기출)

 

[풀이]

맵에 빨간공(R)과 파란공(B)가 있을 때 상하좌우로 기울여서 R을 구멍

O로 10회 이하만에 넣을 수 있는지를 묻는 문제이다.

B가 구멍에 들어가면 실패이며, R과 B가 동시에 들어가도 실패이다.

 

풀이과정

1. 10초 이하로 할 수 있는지 체크하는 문제

2. n번의 기울임으로 R,B가 특정 위치(ry,rx) ,(by,bx)에 처음으로 도달하는 경우가 생겼을 때

   다른 경로로 n번 이상의 기울임으로 올 수 있는 경우는 생각할 필요가 없다.

   어떤 경로로 왔는지와 상관없이 가장 적은 기울임으로 도착했을 때가 무조건 최적이다.

 

=> 1,2를 종합해보면 BFS가 적합하다. visit[ry][rx][by][bx] 로 체크.

 

3. 각 시행마다 4방향씩 기울여보며 시뮬레이션을 해야한다.

   (R,B 좌표를 비교해가며 4방향 각각 시뮬레이션 로직을 구현하면 99% 버그가 생기므로

   이런 문제는 무조건 효율적인 방법을 먼저 생각해야한다.)

 

4. 각 방향마다 구현하지 않기 위해서 dy[4],dx[4] 배열로 4방향에 대한 값을 정의해놓고 이용한다.

5. i:0~3 방향으로 R,B를 굴려본다.

   [B부터 굴린다.]

   1) B를 먼저 굴려서 O를 만나게 되면 무조건 실패이다. (굴러가는중에 앞에 R이 막고있더라도 R이 먼저 O를 통해 빠져나갈 것이므로 R의 위치와 상관없이 위의 경우는 무조건 실패 케이스이다.)

   2) B를 굴리면서 O를 안만난 경우, 굴러간 경로에 R을 만났는지를 체크하고, 벽을 만나면 멈춘다.

   3) 만나는 중에 R을 만났다면 멈춘 위치에서 -dy[i], -dx[i]한 위치가 다음 B의 위치다. 만약 R을 만났다면 벽에는 R이

      붙어있을 것이므로 -2*dy[i],-2dx[i] 한 좌표가 다음 B의 취이다.

 

   [R을 굴린다.]

   1) R을 굴리다 O를 만나면 정답을 찾은 것이다. 1을 출력하고 종료하면 된다.

      (B가 동시에 들어가는 B부터 굴리면서 체크했기 때문에 고려할 필요가 없다.)

   B를 굴릴 때 2),3)과 같이 R도 굴려준다.

 

   새로운 R,B의 위치를 visit 배열에 체크하고 Queue에 넣는다.

 

6. k번째까지 했는데 답이 안나왔으면 답이 없는 것이므로 0을 출력하고 return.

 

#include <cstdio>
#include <queue>
using namespace std;
struct P{
    int ry,rx,by,bx;
};
int N,M;
bool visit[11][11][11][11];
char map[11][11];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int main(){
    scanf("%d%d",&N,&M);
    P p;
    for(int i=0;i<N;i++) 
        for(int j=0;j<M;j++) {
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='R') {
                p.ry=i,p.rx=j;
                map[i][j]='.';
            }
            else if(map[i][j]=='B') {
                p.by=i,p.bx=j;
                map[i][j]='.';
            }
        }
    queue<P> q;
    q.push(p);
    visit[p.ry][p.rx][p.by][p.bx] = 1;
    int k =0;
    while(!q.empty()){
        if(k==10) break;
        int sz = q.size();
        while(sz--){
            P p = q.front(); q.pop();
            for(int i=0;i<4;i++){
                int nby,nbx,nry,nrx;
                int ty=p.by+dy[i],tx=p.bx+dx[i];
                int meet = 0;
                while(map[ty][tx] !='#' && map[ty][tx] != 'O') {
                    if(ty==p.ry&&tx==p.rx) meet = 1;
                    ty+=dy[i],tx+=dx[i];
                }
                if(map[ty][tx]=='O') continue;
                ty-=(1+meet)*dy[i],tx-=(1+meet)*dx[i];
                nby = ty, nbx = tx;
                
                ty=p.ry+dy[i],tx=p.rx+dx[i];
                meet = 0;
                while(map[ty][tx] !='#' && map[ty][tx] != 'O') {
                    if(ty==p.by&&tx==p.bx) meet = 1;
                    ty+=dy[i],tx+=dx[i];
                }          
                if(map[ty][tx]=='O') {
                    puts("1");
                    return 0;
                }
                ty-=(1+meet)*dy[i],tx-=(1+meet)*dx[i];
                nry = ty, nrx = tx;       

                if(!visit[nry][nrx][nby][nbx]){
                    visit[nry][nrx][nby][nbx]=1;
                    q.push({nry,nrx,nby,nbx});
                }
            }
        }
        k++;
    }
    puts("0");
}

 

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13459.cpp