[BOJ 15653] 구슬 탈출 4

#문제

https://www.acmicpc.net/problem/15653

#풀이

해당 문제는 이전에 풀어봤던 두 동전 문제와 비슷하게 풀었습니다.

두 문제 다 두개의 물체를 한번에 움직여야 했고, 판을 움직여 특정 한개의 물체만 뽑아내는 문제입니다.

안풀어 보셨다면 두 동전이라는 문제도 풀어보시는 것을 추천드립니다. :)

또한, 구슬탈출이란 시리즈가 많기 때문에 다른 구슬탈출도 풀어보도록 합시다!

해당 문제에서 주의 깊게 봐야할 것은 구슬의 움직임입니다.

두개의 구슬은 기울여 움직이므로 기울인 방향으로 가지 못할때(벽에 부딪히거나, 탈출구에서 빠졌을때)까지 움직입니다.

또한 겹치지 않기 때문에 움직였을때 조심해야합니다.

주어진 입력 예제를 통해 확인해 봅시다!

#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

해당 입력은 2번째 입력 예제 입니다.

저렇게 두 동전이 같은 선상에 있다고 합시다.

만약 왼쪽으로 기울였다면?

#######
#RB...#
#.#####
#.....#
#####.#
#O....#
#######

위와 같이 되야합니다.

즉, 두개의 공은 겹치지 않아야합니다.

기울일 방향을 보고 미리 처리를 해주어도 되지만, 저의 경우 두 구슬을 다 움직여 놓고 처리를 해주었습니다.

#  #  #####
#(R,B)....#
#  .  #####
#  .  ....#
#  #  ###.#
#  O  ....#
#  #  #####

이렇게 미리 모든 구슬을 다 움직여 놓고 두개의 구슬의 움직인 거리를 구합니다.

R의 경우 3칸을 움직였고, B의 경우에는 4칸을 움직였습니다.

뭔가가 보이시나요? 똑똑하시네요! :)

즉, 많이 움직인 구슬이 적게 움직인 구슬보다 한칸 전에 있다는 것입니다.

따라서 많이 움직인 구슬을 원래 왔던 방향에서 한칸을 뒤로 가게 해줍니다.

다음 위치를 구하고 다음 위치가 방문한 위치인지 확인해주고 큐에 넣어주고를 반복하면 됩니다.

만약 끝까지 답이 구해지지 않는다면 해당 게임은 빨간공을 탈출 시키지 못하므로 -1을 출력해주면 되고,

빨간 공이 탈출했을 시점에서 같이 큐에 집어 넣었던 기울임 횟수를 출력해주시면 끝이 납니다.

#코드

#include <iostream>
#include <queue>
using namespace std;
 
struct Balls{
    int redR,redC,blueR,blueC,cnt = 0;
};
int N,M;
char map[10][10];
bool visit[10][10][10][10];
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
//공 움직이기
void movingBall(int &r, int &c, int &dist, int dr, int dc){
    while(map[r + dr][c + dc] != '#' && map[r][c] != 'O'){
        r += dr;
        c += dc;
        dist += 1;
    }
}
 
void dropTheRedBall(Balls balls){
    queue<Balls> q;
    q.push(balls);
    visit[balls.redR][balls.redC][balls.blueR][balls.blueC] = true;
    while(!q.empty()){
        int redR = q.front().redR;
        int redC = q.front().redC;
        int blueR = q.front().blueR;
        int blueC = q.front().blueC;
        int cnt = q.front().cnt;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nextRedR = redR, nextRedC = redC;
            int nextBlueR = blueR, nextBlueC = blueC;
            int nCnt = cnt + 1;
            //공을 움직일때는 움직인 거리까지 구해주는 이유는 두개의 공이 겹칠 수 있기 때문이다.
            //만약 공들이 같은 선상에 있다고 하자(좌 : 빨강, 우 : 파랑)
            //좌로 기울였다면 빨간공이 파란공보다 왼쪽에 있어야한다.
            //움직인 거리는 빨간공이 파란공 보다 한칸 더 적게 움직였다.
            //따라서 두 공이 같은 위치에 겹쳐있다면 움직인 거리를 보고 많이 움직인 공을 한칸 전으로 움직여주어야 한다.
            int distR = 0, distB = 0;
        
            movingBall(nextRedR, nextRedC, distR, dr[i], dc[i]);
            movingBall(nextBlueR, nextBlueC, distB, dr[i], dc[i]);
            
            //만약 파란공의 위치가 탈출구라면 해당 시도는 무시
            if(map[nextBlueR][nextBlueC] == 'O') continue;
            
            //빨간공이라면 횟수 출력
            if(map[nextRedR][nextRedC] == 'O'){
                cout << nCnt << "\n";
                return;
            }
            
            //빨간공과 파란공이 겹쳤을 경우 위치 조절
            if(nextRedR == nextBlueR && nextRedC == nextBlueC){
                if(distR > distB){
                    nextRedR -= dr[i];
                    nextRedC -= dc[i];
                }else{
                    nextBlueR -= dr[i];
                    nextBlueC -= dc[i];
                }
            }
            //이미 방문했던 위치라면 무시
            if(visit[nextRedR][nextRedC][nextBlueR][nextBlueC]) continue;
            
            //다음 위치를 큐에 넣기
            visit[nextRedR][nextRedC][nextBlueR][nextBlueC] = true;
            Balls b;
            b.redR = nextRedR;
            b.redC = nextRedC;
            b.blueR = nextBlueR;
            b.blueC = nextBlueC;
            b.cnt = nCnt;
            q.push(b);
        }
    }
    cout << -1 << "\n";
}
 
int main(){
    cin >> N >> M;
    Balls balls;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> map[i][j];
            if(map[i][j] == 'R'){
                balls.redR = i;
                balls.redC = j;
            }else if(map[i][j] == 'B'){
                balls.blueR = i;
                balls.blueC = j;
            }
        }
    }
    dropTheRedBall(balls);
    return 0;
}