[백준 13459] 구슬 탈출 C++

문제

백준 13459 구슬 탈출 C++

13459번: 구슬 탈출

풀이

BFS를 사용한다.

방문 체크를 [빨간색 공 x좌표][빨간색 공 y좌표][파란색 공 x좌표][파란색 공 y좌표]로 4차원 배열을 이용한다.

공을 4방향(위, 아래, 왼쪽, 오른쪽)으로 굴려주면서, 방문하지 않았을 때에만 큐에 넣어주고 도착지점에 도달할 수 있을 때까지 반복한다.

그전에 이미 10번 이상 시도했다면 조건에 부합하지 않으므로 0을 출력한다.

 

소스 코드

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
 
int N;
int M;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
char map[10][10];
bool visited[10][10][10][10];
 
struct Node
{
    int x = 0;
    int y = 0;
    int cnt = 0;
};
 
Node Red;
Node Blue;
queue<pair<Node, Node>> q;
 
bool IsRedFirst(Node Red, Node Blue, int dir)
{
    // 왼쪽
    if (dir == 0)
        return (Red.x < Blue.x ? true : false);
    // 오른쪽
    else if (dir == 1)
        return (Red.x > Blue.x ? true : false);
    // 위쪽
    else if (dir == 2)
        return (Red.y < Blue.y ? true : false);
    // 아래쪽
    else
        return (Red.y > Blue.y ? true : false);
}
 
bool Move(Node Red, Node Blue, int dir)
{
    // 1 : 탈출 성공, 2 : 탈출 실패, 0 : 그 외
    int flag = 0;
 
    // 빨강 먼저
    if (IsRedFirst(Red, Blue, dir))
    {
        while (1)
        {
            int nx = Red.x + dx[dir];
            int ny = Red.y + dy[dir];
            
            char next = map[ny][nx];
 
            if (nx == Blue.x && ny == Blue.y)
                break;
            else if (next == '.')
            {
                Red.x = nx;
                Red.y = ny;
            }
            else if (next == 'O')
            {
                flag = 1;
                Red.x = 0;
                Red.y = 0;
                break;
            }
            else
                break;
        }
 
        while (1)
        {
            int nx = Blue.x + dx[dir];
            int ny = Blue.y + dy[dir];
 
            char next = map[ny][nx];
 
            if (nx == Red.x && ny == Red.y)
                break;
            else if (next == '.')
            {
                Blue.x = nx;
                Blue.y = ny;
            }
            else if (next == 'O')
            {
                flag = 2;
                break;
            }
            else
                break;
        }
    }
    // 파랑 먼저
    else
    {
        while (1)
        {
            int nx = Blue.x + dx[dir];
            int ny = Blue.y + dy[dir];
 
            char next = map[ny][nx];
 
            if (nx == Red.x && ny == Red.y)
                break;
            else if (next == '.')
            {
                Blue.x = nx;
                Blue.y = ny;
            }
            else if (next == 'O')
            {
                flag = 2;
                break;
            }
            else
                break;
        }
 
        while (1)
        {
            int nx = Red.x + dx[dir];
            int ny = Red.y + dy[dir];
 
            char next = map[ny][nx];
 
            if (nx == Blue.x && ny == Blue.y)
                break;
            else if (next == '.')
            {
                Red.x = nx;
                Red.y = ny;
            }
            else if (next == 'O')
            {
                if (flag != 2)
                {
                    flag = 1;
                }
 
                break;
            }
            else
                break;
        }
    }
 
 
    if (flag == 1)
        return true;
 
    if (flag == 0 && !visited[Red.x][Red.y][Blue.x][Blue.y])
    {
        Red.cnt++;
        Blue.cnt++;
        q.push({ Red, Blue });
        visited[Red.x][Red.y][Blue.x][Blue.y] = true;
    }
 
    return false;
}
 
bool BFS()
{
    // R, B
    q.push({ Red, Blue });
    visited[Red.x][Red.y][Blue.x][Blue.y] = true;
 
    while (!q.empty())
    {
        Node CurRed = q.front().first;
        Node CurBlue = q.front().second;
        q.pop();
 
        if (CurRed.cnt >= 10)
            return false;
 
        for (int i = 0; i < 4; i++)
        {
            bool result = Move(CurRed, CurBlue, i);
            // 빨간 구슬 목적지
            if (result == true)
                return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string input;
        cin >> input;
 
        for (int j = 0; j < M; j++)
        {
            if (input[j] == 'R')
            {
                Red.x = j;
                Red.y = i;
                map[i][j] = '.';
            }
            else if (input[j] == 'B')
            {
                Blue.x = j;
                Blue.y = i;
                map[i][j] = '.';
            }
            else
            {
                map[i][j] = input[j];
            }
        }
    }
 
    cout << BFS();
 
    return 0;
}