[ 백준 15644 ] 구슬 탈출3 (C++)

백준의 구슬탈출3(15644) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저, 이 문제를 풀기 전에 아직 구슬탈출1과, 구슬탈출2를 풀지 않았다면 먼저 풀어오는 것을 권장한다.

   혹여나 구슬탈출1과 구슬탈출2를 풀지 못했다면 아래의 링크를 타고 풀이법을 읽고 오도록 하자 !

   [ 구슬탈출2 풀이 보러가기 ]

   ( 전체적인 로직이 구슬탈출2와 똑같기 때문에 전체적인 로직 내용 설명은 위의 글로 대체하겠습니다. )

   사실 이 문제 또한, 구슬탈출2와 다른 것이 없다. 풀이가 정말 똑같다. 단지, 정답을 출력함에 있어서 또 다른 요소가

   하나 더 추가되었을 뿐이다.

   바로 움직인 방향을 영어로 출력시켜야 하는 것이다.

   이 부분을 위해서 본인은 Move()함수에 string형 매개변수를 하나 더 추가해주었다.

   그리고 방향을 바꾸면서 Move함수를 호출할 때 마다, 방향에 맞는 영어를 위에서 말한 매개변수에 추가해 주면서

   함수를 호출을 하였다.

   이게 전부이다... 문제의 전체적인 내용이 구슬탈출 1, 2, 3, 4 다 너무 비슷하기 때문에 풀이법에 크게 차이가 나는 것

   같지는 않다..

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cmath>
 
#define endl "\n"
#define MAX 10
#define INF 987654321
using namespace std;
 
int N, M, Answer = INF;
string Answer_Str;
char MAP[MAX][MAX];
pair<int, int> Red, Blue;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
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 Find_Distance(int x, int y, int xx, int yy)
{
    return abs(x - xx) + abs(y - yy);
}
 
int Reverse_Dir(int D)
{
    if (D == 0) return 1;
    else if (D == 1) return 0;
    else if (D == 2) return 3;
    else if (D == 3) return 2;
}
 
string DirToChar(int D)
{
    if (D == 0) return "R";
    else if (D == 1) return "L";
    else if (D == 2) return "D";
    else if (D == 3) return "U";
}
 
void Move(int Rx, int Ry, int Bx, int By, int Dir, int Cnt, string S)
{
    if (Cnt > 10) return;
    if (Cnt > Answer) return;
 
    bool Red_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];
    
    bool Blue_Flag = false;
    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)
        {
            if (Answer > Cnt)
            {
                Answer = Cnt;
                Answer_Str = S;
            }
            return;
        }
    }
 
    if (nRx == nBx && nRy == nBy)
    {
        int Red_Dist = Find_Distance(Rx, Ry, nRx, nRy);
        int Blue_Dist = Find_Distance(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 == Reverse_Dir(Dir)) continue;
        
        Move(nRx, nRy, nBx, nBy, i, Cnt + 1, S + DirToChar(i));
    }
}
 
void Solution()
{
    for (int i = 0; i < 4; i++)
    {
        Move(Red.first, Red.second, Blue.first, Blue.second, i, 1, DirToChar(i));
    }
 
    if (Answer == INF) cout << -1 << endl;
    else
    {
        cout << Answer << endl;
        cout << Answer_Str << 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;
}