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

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

13459번: 구슬 탈출

 
[문제 설명]
10*10 크기의 보드에 빨간 구슬, 파란 구슬, 통과할 구멍이 각각 1개씩 있다.
보드를 기울여서 구슬이 직선으로 움직이고 
빨간 구슬이 10번 이내로 구멍을 통과하면 된다. 이때, 파란 구슬은 통과하면 안됨! 
 
 
[풀이 과정]
처음에 문제를 보고 완전 탐색, DFS를 떠올려서 그렇게 진행을 했다.... 근데 풀 수 없었음.
정확히 말하면, 처음에 문제를 풀 때 DFS를 사용해서 계속 board에다가 R과 B의 위치를 넣어주고 빼면서 둘이 만나는지를 고려해줬는데 이렇게 하니까 지웠다 썼다 하면서 고려할 사항이 너무 많았고 그걸 다 못해서 틀린 것 같다. 
결국엔 다른 블로그 포스팅을 참고해서 풀 수 있었다. 거기엔 BFS로 되어 있어서 나도 동일하게 BFS로 풀었다. 
 

 
참고로 DFS로 풀어도 동일한 방법을 사용했다면 되었을 것.... 뭔가 계속 쓰고 지우고 하는건 더이상 하지 말아야 겠다. 
아니면 전역에 board를 선언해서 같은 board에다가 계속 썼다 지웠다 하지말고 copy를 사용해서 했으면 되었을 것 같다. 시간은 좀 더 걸렸겠지만..
 
문제를 풀면서 고려해줘야 할 건, 둘이 겹치는 경우다. 사실 구슬을 끝까지 이동시키고 bfs를 쓰고 하는건 별로 어렵지도 않고 빼먹을 만한 것도 아닌데 

구슬 둘이 한 방향으로 기울였을 때 나란히 위치한 경우를 고려해줘야 한다. 

 
이 부분만 잘 생각해주면 사실 딱히 헤매는 부분은 없다.... 아이디어를 이상하게 생각하지 않는 이상... 
 
[전체 코드]

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX = 10;

struct Marble {
    int ry, rx, by, bx;
    int r_goal = 0, b_goal=0;
    int prev = -1;
    int cnt = 0;
};

int N, M;
Marble H;
char board[MAX][MAX];

int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

Marble move(Marble now, int i) {
    /*
    int prx = now.rx;
    int pry = now.ry;
    int pbx = now.bx;
    int pby = now.by;
    */
    while (board[now.ry][now.rx] != '#') {
        now.rx += dx[i];
        now.ry += dy[i];
        if (board[now.ry][now.rx] == 'O') {
            now.r_goal = 1;
            break;
        }
    }
    while (board[now.by][now.bx] != '#') {
        now.bx += dx[i];
        now.by += dy[i];
        if (board[now.by][now.bx] == 'O') {
            now.b_goal = 1;
            break;
        }
    }

    now.by -= dy[i];
    now.ry -= dy[i];
    now.bx -= dx[i];
    now.rx -= dx[i];
    now.prev = i;
    now.cnt++;
    return now;

}
int BFS(Marble Marbles) {
    queue<Marble> q;
    q.push(Marbles);

    while (!q.empty()) {
        Marble now = q.front();
        q.pop();

        // cnt 10회 초과면 안됨. 
        if (now.cnt >= 10) continue;
        
        for (int i = 0; i < 4; i++) {
            int rx_prev = now.rx < now.bx ? 1 : 0;
            int ry_prev = now.ry < now.by ? 1 : 0;
            Marble next = move(now, i);
            //파란색 통과하면 이건 더이상 고려하지 않음.
            if (next.b_goal) continue;
            
            // 만약 빨간 공이 통과했다면 return 1
            if (next.r_goal)
            {
                //cout << "x :"<<next.bx << " y:" << next.by << '\n';
                return 1;
            }

            if (next.ry == next.by && next.rx == next.bx) {
                if (now.ry == now.by) {
                    //빨간색이 왼쪽에 있고 왼쪽으로 기울일 때거나 빨간색이 오른쪽이고 오른쪽으로
                    if ((rx_prev && i == 2) || (!rx_prev && i == 3)) next.bx -= dx[i];
                    // 빨간색이 왼쪽에 있고 오른쪽으로 기울일 때거나 빨간색이 오른쪽이고 왼쪽으로
                    else if ((rx_prev && i == 3) || (!rx_prev && i == 2)) next.rx -= dx[i];
                }
                else if (now.rx == now.bx) {
                    //빨간색이 위쪽에 있고 위쪽으로 기울일 때거나 빨간색이 아래쪽이고 아래로
                    if ((ry_prev && i == 0) || (!ry_prev && i == 1)) next.by -= dy[i];
                    // 빨간색이 위쪽에 있고 아래쪽으로 기울일 때거나 빨간색이 아래이고 위쪽으로
                    else if ((ry_prev && i == 1) || (!ry_prev && i == 0)) next.ry -= dy[i];
                }
            }
            
            if(next.cnt<=10) q.push(next);
        }
    }
    return 0;

}

int main() {
    cin >> N >> M;

    Marble Marbles;

    for (int y = 0; y < N; y++) {
        for (int x = 0; x < M; x++) {
            cin >> board[y][x];
            if (board[y][x] == 'B') { Marbles.bx = x; Marbles.by = y; }
            else if (board[y][x] == 'R') { Marbles.rx = x; Marbles.ry = y; }
        }
    }

    cout << BFS(Marbles);

}

 
 
 
https://www.youtube.com/watch?v=SarTy3ZwmVo