[백준 13460] 구슬 탈출 2

 

 그래프 탐색 문제다. 최소로 움직이는 횟수를 구해야 하니 BFS가 유리한 측면이 있으나, 최대 깊이가 10으로 그다지 깊지 않고 오늘따라 recursive call이 땡겨서 DFS로 구현했다.

 

 문제에 제시되는 그대로 구현하는 시뮬레이션 문제이기도 해서, 복잡한 로직은 필요하지 않다. 나는 구슬을 움직이는 함수를 먼저 만들었다. 보드의 크기가 컸다면 미리 벽의 좌표들을 저장해두고 이진 탐색으로 구슬이 이동할 위치를 결정했을 것 같지만, 보드의 세로와 가로 크기는 둘다 최대 10으로 상당히 작다. 그래서 구슬의 위치로부터 정해진 방향으로 선형 탐색을 통해 구슬이 멈출 위치를 찾도록 했다.

 구슬이 멈출 위치를 찾았다면, 기존 구슬의 위치는 빈 공간으로 만들어 주고 구슬이 구멍으로 빠지는 경우인지 검사한다. 구슬이 빠지지 않았다면 새로 멈춘 위치에 구슬을 표시해준다. 이후에는 구슬이 빠졌는지 여부와 새로운 구슬의 위치를 리턴하는 형태로 함수를 종료한다.

 

 그 다음엔 실질적으로 DFS를 통해 탐색하는 함수를 구현했다. 입력 받은 보드를 상하좌우로 기울이는 동작을 구현한다. 각 방향별로 구슬을 움직이는 함수를 호출하는데, 이 때 조금 유의해야 하는 것은 어느 색 구슬을 먼저 움직이느냐이다. 문제에서는 구슬이 동시에 움직인다고 하고 있으므로, 이를 고려해주어야 한다. 나란히 있는 두 구슬을 나란한 방향으로 기울였을 때 구슬들이 순서를 유지한 채 벽에 붙는 형태가 되므로, 기울이는 방향쪽에 가까운 구슬을 먼저 이동시키고 뒤이어 먼 쪽의 구슬을 이동시켜 의도한 동작을 만족시킬 수 있다. 물론, 두 구슬이 나란히 놓여진 방향으로 기울이는 것이 아니거나 두 구슬이 나란히 위치한 것이 아니라면 뭘 먼저 움직이든, 그 결과는 멱등하다.

 

 구슬을 움직일 순서까지 결정해, 위에서 만들었던 구슬을 움직이는 함수까지 호출 했다면 그 결과를 확인한다. 일단 파란 구슬이 구멍으로 빠졌다면 더 이상 탐색할 이유가 없다. 파란 구슬이 빠지지 않고, 빨간 구슬만 구멍으로 빠졌다면 이 방법이 정답이 될 수 있으므로, 전역변수로 생성해둔 최소 움직임 횟수를 갱신해준다. 이 경우에도, 더 이상의 탐색은 필요없다.

 여기도 해당되지 않는다면, 파란 구슬과 빨간 구슬이 둘 다 구멍으로 빠지지 않은 경우다. 이 때, 빨간 구슬과 파란 구슬의 새 위치가 보드를 기울이기 전과 동일하다면, 더 탐색할 이유가 없으므로 이 때도 탐색을 진행하지 않는다.

 그런 경우도 아니라면, depth를 확인해 10보다 작지 않다면 recursive call로 다음 depth를 진행한다. 그리고 함수의 시작부분에는 현재까지 찾아낸 최소 움직임 횟수와 DFS로 탐색 중인 depth(움직임 횟수)를 비교해, depth가 더 작을 때만 함수를 진행하도록 해서 불필요한 탐색을 더 좀 더 줄여준다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> point;
typedef pair<bool, point> ball_result;

int n, m;
int minDepth = 11;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

ball_result moveBall(vector<vector<char> >& board, point p, int dir, bool isRed) {
    int curY = p.first;
    int curX = p.second;

    while(board[curY+dy[dir]][curX+dx[dir]] == '.') {
        curY += dy[dir];
        curX += dx[dir];
    }

    board[p.first][p.second] = '.';
    if(board[curY+dy[dir]][curX+dx[dir]] == 'O') {
        return {true, {curY+dy[dir], curX+dx[dir]}};
    } else {
        board[curY][curX] = isRed ? 'R' : 'B';
        return {false, {curY, curX}};
    }
}

void solve(vector<vector<char> > board, point blue, point red, int depth) {
    if(depth>=minDepth) return;

    for(int i=0; i<4; i++) {
        vector<vector<char> > newBoard(board);
        
        ball_result redResult, blueResult;
        if(
            (i==0 && blue.second>red.second) ||
            (i==1 && blue.first>red.first) ||
            (i==2 && blue.second<red.second) ||
            (i==3 && blue.first<red.first)
        ) {
            blueResult = moveBall(newBoard, blue, i, false);
            redResult = moveBall(newBoard, red, i, true);
        } else {
            redResult = moveBall(newBoard, red, i, true);
            blueResult = moveBall(newBoard, blue, i, false);            
        }

        if(blueResult.first) continue;;
        if(redResult.first) {
            minDepth = min(minDepth, depth);
            return;
        }
        if(blueResult.second == blue && redResult.second == red) continue;
        if(depth < 10) {
            solve(newBoard, blueResult.second, redResult.second, depth+1);
        } 
    }
}

int main() {
    cin >> n >> m;

    vector<vector<char> > board = vector<vector<char> >(n, vector<char>(m));
    point red, blue;

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> board[i][j];
            if(board[i][j] == 'R') {
                red = {i, j};
            } else if(board[i][j] == 'B') {
                blue = {i, j};
            }
        }
    }

    solve(board, blue, red, 1);

    cout << (minDepth==11?-1:minDepth);
}