[ 백준 15653 ] 구슬 탈출4 (C++)

백준의 구슬탈출4(15653) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 구슬탈출 시리즈의 4번째, 구슬탈출4 문제이다. 이전의 구슬탈출 시리즈들(1, 2, 3)은 모두 DFS로 풀어보았지만,

   이 문제는 DFS로 탐색할 경우 본인의 코드는 재귀에서 빠져 나오지 못하는 문제점이 있어서 BFS로 풀어보았다.

   하지만, 탐색하는 그 중간 과정은 DFS와 동일하고, 본인이 풀었던 이전 시리즈들의 로직과 똑같기 때문에

   이 로직을 이 글에서는 설명하지 않겠다.

   [ 구슬탈출2 풀이 바로가기(로직 설명) ]

   BFS에 사용되는 Queue에서 관리하는 변수는 총 5개를 사용하였다.

   { 빨간공 x좌표 , 빨간공 y좌표 , 파란공 x좌표 , 파란공 y좌표 , 움직인횟수 }

   이렇게 5개를 관리해 주었다.

   위에서 말했듯이 BFS에서 탐색을 하는 과정은 이전 시리즈들의 로직과 똑같은 방법으로 탐색을 진행해 주었고

   BFS에서 가장 중요한 방문 체크는 4차원배열 Visit[][][][] 를 만들어서 관리해주었다.

   4차원 배열로 만든 이유는, Visit[Red_x][Red_y][Blue_x][Blue_y] 이런식으로 빨간공과 파란공이 움직이는 좌표를

   함께 관리해주기 위함이다. 빨간공만 관리할 경우, 방문 처리가 제대로 되지 않을 수 있기 때문에 빨간공 파랑공의

   좌표를 함께 관리하기 위해서 4차원으로 만들어 주었다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cmath>
#include<queue>
 
#define endl "\n"
#define MAX 10
#define INF 987654321
using namespace std;
 
int N, M, Answer = INF;
string Answer_Str;
char MAP[MAX][MAX];
bool Visit[MAX][MAX][MAX][MAX];
pair<int, int> Red, Blue;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
struct INFO
{
    int Rx, Ry;
    int Bx, By;
    int Cnt;
};
 
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);
}
 
void BFS()
{
    queue<INFO> Q;
    Q.push({ Red.first, Red.second, Blue.first, Blue.second, 0 });
    Visit[Red.first][Red.second][Blue.first][Blue.second] = true;
 
    while (Q.empty() == 0)
    {
        int Rx = Q.front().Rx;
        int Ry = Q.front().Ry;
        int Bx = Q.front().Bx;
        int By = Q.front().By;
        int Cnt = Q.front().Cnt;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            bool RedFlag, BlueFlag;
            RedFlag = BlueFlag = false;
 
            int nRx = Rx + dx[i];
            int nRy = Ry + dy[i];
            int nBx = Bx + dx[i];
            int nBy = By + dy[i];
            int nCnt = Cnt + 1;
 
            while (1)
            {
                if (MAP[nRx][nRy] == '#') break;
                if (MAP[nRx][nRy] == 'O')
                {
                    RedFlag = true;
                    break;
                }
                nRx = nRx + dx[i];
                nRy = nRy + dy[i];
            }
            nRx = nRx - dx[i];
            nRy = nRy - dy[i];
 
            while (1)
            {
                if (MAP[nBx][nBy] == '#') break;
                if (MAP[nBx][nBy] == 'O')
                {
                    BlueFlag = true;
                    break;
                }
                nBx = nBx + dx[i];
                nBy = nBy + dy[i];
            }
            nBx = nBx - dx[i];
            nBy = nBy - dy[i];
 
            if (BlueFlag == true) continue;
            if (RedFlag == true)
            {
                cout << nCnt << endl;
                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[i];
                    nRy = nRy - dy[i];
                }
                else
                {
                    nBx = nBx - dx[i];
                    nBy = nBy - dy[i];
                }
            }            
            if (Visit[nRx][nRy][nBx][nBy] == true) continue;
            Visit[nRx][nRy][nBx][nBy] = true;
            Q.push({ nRx, nRy, nBx, nBy, nCnt });            
        }
    }
    cout << -1 << endl;
}
 
void Solution()
{
    BFS();
}
 
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;
}