백준 #13460 구슬 탈출 2

백준 #13460 구슬 탈출 2

빨간 구슬과 파란 구슬이 있는 판을 기울여 빨간 구슬이 구멍에 빠지게 하는 최소 기울임 횟수를 구하는 문제.

BFS를 사용하여 최소 횟수를 구할 수 있다.

구슬이 두 개여서 한 번 기울일 때마다 두 구슬의 좌표를 각각 구해주고 겹치지 않게 해주어야 한다.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

int N, M;
char board[10][10];
int visit[10][10][10][10];     //빨간 구슬, 파란 구슬의 좌표에 따른 판 기울임 횟수
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void emptyBuffer() {           // '\n' 캐릭터 소모
    while(getchar() != '\n') {}
}

bool redLater(pair<int, int> rPos, pair<int, int> bPos, int dir) { //빨간 구슬이 늦게 굴렀는지 반환
    bool isRedLater = false;
    if(dir == 0 && rPos.second < bPos.second) {
        isRedLater = true;
    }
    else if(dir == 1 && rPos.second > bPos.second) {
        isRedLater = true;
    }
    else if(dir == 2 && rPos.first < bPos.first) {
        isRedLater = true;
    }
    else if(dir == 3 && rPos.first > bPos.first) {
        isRedLater = true;
    }
    return isRedLater;
}

/* 입력: 빨간 구슬의 x, y 좌표, 파란 구슬의 x, y 좌표
   출력: 빨간 구슬을 구멍에 넣을 수 있는 최소 판 기울임 횟수(10 초과인 경우 -1) */
int bfs(int rx, int ry, int bx, int by) {
    queue<pair<pair<int, int>, pair<int, int>>> q;
    q.push({{rx, ry}, {bx, by}});
    visit[rx][ry][bx][by] = 0;
    while(!q.empty()) {
        pair<int, int> tmpR = q.front().first;
        pair<int, int> tmpB = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++) {
            int rNx = tmpR.first;
            int rNy = tmpR.second;
            int bNx = tmpB.first;
            int bNy = tmpB.second;
            int depth = visit[rNx][rNy][bNx][bNy];  //판의 기울임 횟수
            if(depth > 9) {
                break;
            }
            bool redInHole = false;
            bool bluInHole = false;
            while(board[rNx][rNy] != '#') {        //빨간 구슬이 벽을 만날 때까지 탐색
                if(board[rNx][rNy] == 'O') {
                    redInHole = true;
                    break;
                }
                rNx += dx[i];
                rNy += dy[i];
            }
            if(!redInHole) {                     //벽을 만난 경우 좌표 - 1
                rNx -= dx[i];
                rNy -= dy[i];
            }
            while(board[bNx][bNy] != '#') {      //파란 구슬이 벽을 만날 때까지 탐색
                if(board[bNx][bNy] == 'O') {
                    bluInHole = true;
                    break;
                }
                bNx += dx[i];
                bNy += dy[i];
            }
            if(!bluInHole) {                     //벽을 만난 경우 좌표 - 1
                bNx -= dx[i];
                bNy -= dy[i];
            }
            if(rNx == bNx && rNy == bNy && !redInHole) {      //빨간 구슬과 파란 구슬의 좌표가 겹칠 시 나중에 온 구슬의 좌표 - 1
                if(redLater(tmpR, tmpB, i)) {
                    rNx -= dx[i];
                    rNy -= dy[i];
                }
                else {
                    bNx -= dx[i];
                    bNy -= dy[i];
                }
            }
            if(redInHole && !bluInHole) {                    //빨간 구슬은 구멍에 들어가고 파란 구슬은 구멍에 들어가지 않을 시 depth + 1 반환
                return depth + 1;
            }
            if(!bluInHole && visit[rNx][rNy][bNx][bNy] == -1) { //파란 구슬이 구멍에 들어가지 않고 visit한 적이 없을 시 queue에 push
                q.push({{rNx, rNy}, {bNx, bNy}});
                visit[rNx][rNy][bNx][bNy] = depth + 1;
            }

        }
    }
    return -1;                                        //10번 초과 기울여도 빨간 구슬을 구멍에 넣을 수 없을 시 -1 반환
}


int main() {
    memset(visit, -1, sizeof(visit));
    cin >> N >> M;
    int rX, rY, bX, bY;
    emptyBuffer();
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            board[i][j] = getchar();
            if(board[i][j] == 'R') {
                rX = i;
                rY = j;
                board[i][j] = '.';
            }
            else if(board[i][j] == 'B') {
                bX = i;
                bY = j;
                board[i][j] = '.';
            }
        }
        emptyBuffer();
    }
    cout << bfs(rX, rY, bX, bY);
    
    return 0;
}