[BOJ] C++ 13460: 구슬 탈출 2 - 백트래킹을 이용한 시뮬레이

13460번: 구슬 탈출 2

---

문제 분석부터 해보자. N * M 크기 보드에 파란 구슬, 빨간 구슬이 하나씩 있고 상하좌우 기울여서 구슬이 구멍에 들어가는지 관찰하면 된다. 빨간색만 빠지면 성공이고 빨, 파 동시에 빠지거나 파란색만 빠지면 실패이다. 10번 이상 움직여도 실패이다. 

 

문제를 보고 예제들을 한 번 훑어보면서 생각난 주의 사항은 다음과 같다.

1. 공 하나가 구멍에 빠지는 경우를 주의하자. (예제 7)
2. 움직일 때 두 공이 겹칠 수 없다.
3. 공이 움직일 수 없는 경우 더 이상 진행할 필요가 없다. 하지만 시간 복잡도가 여유롭면 이 부분은 구현할 필요가 없다.
4. 그리디 하게 상하좌우로 움직이면 안 된다. 파란색 공을 구석에 박아놓고 빨간색만 움직일 수 있다. 
   
   

1, 2번 주의사항은 판을 기울이는 함수를 짤 때 도움이 될 것 같고, 4번 주의사항에서 알고리즘을 떠올렸다.

그리디 하게 움직일 수 없다면 완전 탐색으로 접근해야 하는데, 파란색이 빠지는 경우를 가지치기하는 백트래킹 알고리즘으로 생각해 두고 시간복잡도를 계산해 봤다. 총 4^10 만큼의 경우의 수가 있고, 한 케이스당 대략 10번의 연산이 있으므로 천만번정도의 연산이 일어난다. 2초 안에 무조건 가능하므로 백트래킹을 이용한 완전 탐색으로 구현을 시작했다.

 

구현해야 하는 사항은 다음과 같다.

1. 판 기울이기
2. 기울인 후 성공/실패 판별
3. 모든 케이스 관찰하기
   • 모든 케이스를 관찰하는 부분은 이미 감시 문제에서 재귀로 구현한 적이 있어서 재귀로 구현했다.

우선 판을 기울이는 부분부터 구현했다. 처음에는 상하좌우 이동 함수를 모두 만들어서 공이 존재하는 행/열을 독립적으로 보고 이동시키려 했다. 그렇게 구현하다가 비효율적인 부분이 많이 보였다. 먼저 R, B가 같은 라인에 존재하는 경우 둘 중 옮기는 방향에 따라 먼저 옮길 공을 정하고 옮겨야 하는데, 차라리 둘 다 옮기고 겹치는 경우만 늦게 옮긴 쪽을 반대 방향으로 되돌리는 편이 나을 것 같아서 그 부분을 수정했다. 그런데 또 이렇게 수정하다 보니 느낀 게 R, B가 서로 독립적으로 장애물의 영향만 받아서 옮겨졌다는 것이었다. 여기서 떠올린 게 R, B 위치만 기억해 두고 board에는 그냥 장애물, 빈칸, 구멍만 두는 방법이다. 이렇게 하면 보드를 기울일 때마다 R, B 위치를 보드에서 수정할 필요 없이 상수 시간으로 R, B 위치만 수정하면 된다. 두 번째 수정 사항을 모르고 그냥 보드에서 계속 수정하면서 진행해도 시간은 비슷하게 걸릴 것 같긴 하다.

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

int move(int dir)
{
    int n_rx = r.first, n_ry = r.second, n_bx = b.first, n_by = b.second;
    // 파란색부터 이동
    while (board[n_bx + dx[dir]][n_by + dy[dir]] == '.')
    {
        // 다음 칸이 점인 동안만 이동
        n_bx += dx[dir];
        n_by += dy[dir];
    }
    // 파란색 다음 칸이 구멍이라면 탙출 실패, false 리턴
    // 파란색 칸만 보고 구멍에 들어갈 수 있다면 바로 실패로 판정해도 되는 이유는
    // 어차피 dir 방향으로 굴렸을 때 빨, 파가 같은 라인에 있어도 빨간색 때문에 파란색이 못 들어가는 경우가 없기 때문이다.
    if (board[n_bx + dx[dir]][n_by + dy[dir]] == 'O')
        return -1;

    // 빨간색 이동
    while (board[n_rx + dx[dir]][n_ry + dy[dir]] == '.')
    {
        // 다음 칸이 점인 동안만 이동
        n_rx += dx[dir];
        n_ry += dy[dir];
    }
    // 빨간색 다음 칸이 구멍이라면 탈출 성공
    if (board[n_rx + dx[dir]][n_ry + dy[dir]] == 'O')
        return 1;

    // 두 공이 겹쳐져있다면 늦게 온 칸 dir 반대 방향으로 이동
    if ((n_rx == n_bx) && (n_ry == n_by))
    {
        if (dir == 0)
            // 원래 b의 x좌표가 더 크다면 b가 늦게 온 것
            // 현재 dir 방향이 행 감소, 즉 위쪽이므로 늦게 온 것 아래로 이동
            r.first < b.first ? n_bx++ : n_rx++;
        else if (dir == 1) // 현재 dir 방향 아래
            r.first > b.first ? n_bx-- : n_rx--;
        else if (dir == 2) // 현재 dir 방향 왼쪽
            r.second < b.second ? n_by++ : n_ry++;
        else // 왼쪽
            r.second > b.second ? n_by-- : n_ry--;
    }
    r = {n_rx, n_ry};
    b = {n_bx, n_by};
    return 0;
}

 

다음은 모든 케이스를 탐색하는 부분인데, 많이 해봐서 쉽게 구현했다. 항상 재귀를 구현할 땐 함수 정의, base condition, 재귀식을 먼저 구성해놓고 구현한다.

• 함수 정의
  void func(int cnt) : 현재 cnt번만큼의 이동이 구현된 상태이고 함수에 들어가면 cnt + 1 번째 이동이 시작된다.
• base condition
  if(cnt >= 10) return;
• 재귀식
  dir에 맞게 상하좌우 이동 함수 호출(move(dir)) -> 함수의 리턴값에 따라 성공/실패 판별 -> 이동이 성공했으면 func(cnt + 1); -> 호출이 끝나면 board 복구, 이 문제에서는 R, B의 위치만 복구하면 됨

위 사항들을 그대로 구현해주면 된다.

void func(int cnt)
{
    // 현재 cnt번의 이동까지 구현 완료, cnt 10이면 10번 이동 완료인데 통과가 안됐으므로 종료
    if (cnt >= 10)
        return;

    for (int dir = 0; dir < 4; dir++)
    {
        auto tmp_r = r, tmp_b = b;
        int flag = move(dir);
        if (flag == -1)
            continue;
        else if (flag == 1)
        {
            ans_min = min(ans_min, cnt + 1);
            continue;
        }
        else
            func(cnt + 1);
        r = tmp_r;
        b = tmp_b;
    }
}

 

이제 합쳐주면 코드는 끝이다. 나는 최대 이동이 10번이라는 점과 가지치기를 할 케이스가 많이 보인다는 점, 비슷한 완전 탐색을 재귀로 구현했다는 점을 근거로 재귀를 이용한 백트래킹으로 구현을 했는데, BFS로도 풀이가 가능했다. dist [rx][ry][bx][by] = 공들을 (rx, ry), (bx, by)까지 이동하는데 걸리는 횟수로 두고 bfs를 돌리는 풀이인데, 탐색이라는 점에서 사차원 배열을 응용해서 만든 풀이인 것 같다. 4차원 배열을 어떻게 사용할지만 생각하면 다른 문제에서도 두고두고 쓸 수 있을 것 같으니 꼭 bfs를 이용한 풀이도 알아두자.

/** 시뮬레이션 13460 구슬 탈출 2 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m, ans_min = 100;
char board[11][11];
pair<int, int> r, b;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int move(int dir)
{
    int n_rx = r.first, n_ry = r.second, n_bx = b.first, n_by = b.second;
    // 파란색부터 이동
    while (board[n_bx + dx[dir]][n_by + dy[dir]] == '.')
    {
        // 다음 칸이 점인 동안만 이동
        n_bx += dx[dir];
        n_by += dy[dir];
    }
    // 파란색 다음 칸이 구멍이라면 탙출 실패, false 리턴
    // 파란색 칸만 보고 구멍에 들어갈 수 있다면 바로 실패로 판정해도 되는 이유는
    // 어차피 dir 방향으로 굴렸을 때 빨, 파가 같은 라인에 있어도 빨간색 때문에 파란색이 못 들어가는 경우가 없기 때문이다.
    if (board[n_bx + dx[dir]][n_by + dy[dir]] == 'O')
        return -1;

    // 빨간색 이동
    while (board[n_rx + dx[dir]][n_ry + dy[dir]] == '.')
    {
        // 다음 칸이 점인 동안만 이동
        n_rx += dx[dir];
        n_ry += dy[dir];
    }
    // 빨간색 다음 칸이 구멍이라면 탈출 성공
    if (board[n_rx + dx[dir]][n_ry + dy[dir]] == 'O')
        return 1;

    // 두 공이 겹쳐져있다면 늦게 온 칸 dir 반대 방향으로 이동
    if ((n_rx == n_bx) && (n_ry == n_by))
    {
        if (dir == 0)
            // 원래 b의 x좌표가 더 크다면 b가 늦게 온 것
            // 현재 dir 방향이 행 감소, 즉 위쪽이므로 늦게 온 것 아래로 이동
            r.first < b.first ? n_bx++ : n_rx++;
        else if (dir == 1) // 현재 dir 방향 아래
            r.first > b.first ? n_bx-- : n_rx--;
        else if (dir == 2) // 현재 dir 방향 왼쪽
            r.second < b.second ? n_by++ : n_ry++;
        else // 왼쪽
            r.second > b.second ? n_by-- : n_ry--;
    }
    r = {n_rx, n_ry};
    b = {n_bx, n_by};
    return 0;
}

void func(int cnt)
{
    // 현재 cnt번의 이동까지 구현 완료, cnt 10이면 10번 이동 완료인데 통과가 안됐으므로 종료
    if (cnt >= 10)
        return;

    for (int dir = 0; dir < 4; dir++)
    {
        auto tmp_r = r, tmp_b = b;
        int flag = move(dir);
        if (flag == -1)
            continue;
        else if (flag == 1)
        {
            ans_min = min(ans_min, cnt + 1);
            continue;
        }
        else
            func(cnt + 1);
        r = tmp_r;
        b = tmp_b;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

            if (board[i][j] == 'B')
            {
                board[i][j] = '.';
                b = {i, j};
            }
        }
    }

    func(0);
    if (ans_min == 100)
        cout << "-1\n";
    else
        cout << ans_min << '\n';
}