[ 백준 13460 ] 구슬 탈출2 (C++)

백준의 구슬탈출2(13460) 문제이다.

[ 문제 바로가기 ]

- 13459번 문제인 구슬탈출 문제에 대한 풀이는 아래와 같습니다. 사실 정답을 출력시키는 것만 다르고 모든 풀이법이

   똑같기 때문에 아래 설명을 읽으시면 13459번 구슬탈출 문제도 푸실 수 있을 것입니다. -

[ 구슬탈출(13459) 바로가기 ]

[ 문제풀이 ]

1) 본인은 이 문제를 재귀를 통한 완전탐색으로 진행해 보았다. 어떤식으로 진행이 되는지 천천히 알아보자.

    가장 먼저, 빨간공 파란공이 있는 위치에서 동서남북 총 4방향으로 움직여보는 것을 시작으로 한다.

    참고로 본인은 맵에서 R과 B는 없애버렸고 그 좌표만으로 모든 것을 계산해 주었다.

    움직이는 함수의 진행과정은 다음과 같다.

    1. 빨간공을 진행방향으로 움직인다. 이 과정에서 빨간공이 구멍에 빠지게 되면 구멍에 빠졋다고 표시를 해준다.

    2. 파란공을 진행방향으로 움직인다. 이 과정에서 파란공이 구멍에 빠지게 되면 구멍에 빠졌다고 표시를 해준다.

    3. 파란공이 구멍에 빠졌다면 그대로 그 함수를 끝내준다.

       왜냐하면 빨간공이 빠지든 말든 상관없이 파란공이 빠졌다는 것은 잘못된 방향으로 움직였다는 의미이기 때문이다.

    4. 파란공이 구멍에 빠지지 않았는데 빨간공이 빠졌다면 기존의 기울인 횟수와 비교해서 값을 갱신시켜준다.

    5. 위의 두 경우 모두 아니라면, 즉 그 어떤공도 구멍에 빠지지 않았다면 빨간공과 파란공의 좌표를 비교해준다.

        갑자기 왜 좌표를 비교할까?? R과 B가 겹쳐지는 경우가 존재할 수 있기 때문이다. 물론 이건 본인 처럼 구현했을

        때이다. 처음에 말했듯이 본인의 맵에서 R과 B는 없다. 오직 '#' , '.' , 'O' 뿐이다.

        따라서, 두 공 모두 구멍에 빠지지 않았다면 벽에 부딪혀서 멈추게 된 경우일 것이다.

        #RB...# 이런 맵이 있을 때 이거를 본인의 맵으로 바꿔보면 #.....# 이 될 것이고 오른쪽으로 기울였을 때 결과상태는

        #...RB# 가 될 것이다. 하지만, 본인의 맵에서는 아마 R과 B가 겹쳐있는 형태일 것이다.

       따라서, 빨간공과 움직인 거리와 파란공이 움직인 거리를 비교해서 더 많이 움직인 놈을 한칸 뒤로 땡겨주었다.

       위의 경우로 설명을 하자면, R은 총 4칸을 움직였고 B는 3칸을 움직였다. 즉, R이 더 많이 움직였으므로

       한 칸 뒤로 땡겨서 #...RB#와 같은 형태로 만들어준 것이다.

    6. 위의 과정이 끝났으면 움직인 R과 B의 좌표로 움직이는 함수를 재귀적으로 호출하는데 이 때는 방향을 신경써주어야

        한다.

        생각을 해보자. 우리가 예를 들어 오른쪽으로 공을 움직였다고 생각해보자. 그 다음 턴에서 왼쪽으로 공을 움직이는게

        의미가 있을까?? 아니다. 다시 제자리로 돌아가는 움직임이기 때문에 의미가 없다.

        또한 이 상태에서 오른쪽으로 또 움직이는것 또한 의미가 있을까?? 아니다. 지금 오른쪽으로 더 이상 갈 곳이 없어서

        멈춰있는 상태인데 이 상태에서 오른쪽으로 또 움직이는 것은 의미가 없다.

        즉, 현재 움직인 방향과, 현재 움직인 방향의 반대방향으로는 그 다음 턴에서는 움직일 수 없게 해 주었다.

2) 위의 내용을 재귀로 호출하면서 반복하면된다. 물론 10번이상 움직인 경우는 의미가 없으므로, 현재 움직인 횟수가 10번

    이상이면 탐색할 것도 없이 return 시켜주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
int N, M, Answer = 987654321;
char MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
pair<int, int> Red, Blue;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'R')
            {
                Red.first = i;
                Red.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'B')
            {
                Blue.first = i;
                Blue.second = j;
                MAP[i][j] = '.';
            }
        }
    }
}
 
int Move_Dist(int x, int y, int xx, int yy)
{
    return abs(x - xx) + abs(y - yy);
}
 
int Inverse_Direction(int Cur_D)
{
    if (Cur_D == 0) return 1;
    else if (Cur_D == 1) return 0;
    else if (Cur_D == 2) return 3;
    else if (Cur_D == 3) return 2;
}
 
void Move(int Rx, int Ry, int Bx, int By, int Cnt, int dir)
{
    if (Cnt >= Answer) return;
    if (Cnt > 10) return;
 
    bool Red_Flag = false;
    bool Blue_Flag = false;
 
    int nRx = Rx + dx[dir];
    int nRy = Ry + dy[dir];
    while (1)
    {
        if (MAP[nRx][nRy] == '#') break;
        if (MAP[nRx][nRy] == 'O')
        {
            Red_Flag = true;
            break;
        }
        nRx = nRx + dx[dir];
        nRy = nRy + dy[dir];
    }
    nRx = nRx - dx[dir];
    nRy = nRy - dy[dir];
 
    int nBx = Bx + dx[dir];
    int nBy = By + dy[dir];
    while (1)
    {
        if (MAP[nBx][nBy] == '#') break;
        if (MAP[nBx][nBy] == 'O')
        {
            Blue_Flag = true;
            break;
        }
        nBx = nBx + dx[dir];
        nBy = nBy + dy[dir];
    }
    nBx = nBx - dx[dir];
    nBy = nBy - dy[dir];
 
    if (Blue_Flag == true) return;
    else
    {
        if (Red_Flag == true)
        {
            Answer = Min(Answer, Cnt);
            return;
        }
    }
 
    if (nRx == nBx && nRy == nBy)
    {
        int Red_Dist = Move_Dist(Rx, Ry, nRx, nRy);
        int Blue_Dist = Move_Dist(Bx, By, nBx, nBy);
 
        if (Red_Dist > Blue_Dist)
        {
            nRx = nRx - dx[dir];
            nRy = nRy - dy[dir];
        }
        else
        {
            nBx = nBx - dx[dir];
            nBy = nBy - dy[dir];
        }
    }
 
 
    for (int i = 0; i < 4; i++)
    {
        if (i == dir) continue;
        if (i == Inverse_Direction(dir)) continue;
 
        Move(nRx, nRy, nBx, nBy, Cnt + 1, i);
    }
}
 
void Solution()
{
    for (int i = 0; i < 4; i++)
    {
        int x = Red.first;
        int y = Red.second;
        int xx = Blue.first;
        int yy = Blue.second;
 
        Move(x, y, xx, yy, 1, i);
    }
 
    if (Answer > 10 || Answer == 987654321) Answer = -1;
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}