[백준] 13460번 : 구슬 탈출 2 - C++

백준 13460번 : 구슬 탈출 2

등급 : Gold I

13460번: 구슬 탈출 2 (acmicpc.net)

13460번: 구슬 탈출 2

사용 알고리즘 : BFS

사용 자료구조 : Vector, Queue

 

BFS를 이용해 최단 거리, 4차원 Visit 배열(빨간 공, 파란 공 각각의 좌표)을 이용하여 해결.

고려해야 할 요인이 꽤 많은 문제였다.

공이 굴러간 위치를 어떻게 지정할까 고민하다 같이 끝까지 굴리고 이후에 겹칠 경우 위치를 다시 잡아주었다.

 

[ 고려해야 할 케이스 ]

 1. 두 공이 벽까지 굴러갔을 때 위치가 겹칠 경우
   : 두 공을 벽이 있는 곳까지 이동시켰을 때 Red와 Blue가 겹치는 경우 본래 있던 위치를 고려해 Red와 Blue 위치 재지정

 2. 두 공이 동시에 구멍에 빠진 경우

   : 두 공이 동시에 구멍이 빠진 경우의 케이스는 건너뛰도록 설정

 

 3. 파란 공이 먼저 구멍에 빠진 경우

   : 이 경우 역시 건너뛰도록 설정

 

처음에는 건너뛰도록 구현하지 않고 구멍에 빠지면 바로 -1을 출력하였으나 아래와 같은 반례가 존재.

 

← ↓ → ↓ → ↓ ←의 7단계로 들어갈 수 있게 됨.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector <vector <char>> v;
bool visit[11][11][11][11] = { false };
// 파란 구슬과 빨간 구슬의 좌표를 저장할 4차원 배열

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

struct ball_Status
// 구슬의 위치 정보를 저장하기 위한 구조체
{
    int r_x;
    int r_y;
    int b_x;
    int b_y;
    int move = 0;

    void input_Red(int r_x, int r_y)
    {
        this->r_x = r_x;
        this->r_y = r_y;
    }
    void input_Blue(int b_x, int b_y)
    {
        this->b_x = b_x;
        this->b_y = b_y;
    }
};
ball_Status init;
// 처음 위치를 저장할 ball_Status 구조체 init

ball_Status move_Towards(int i, ball_Status b)
// 이동된 구슬 위치를 return해줄 move_Towards 함수
{
    int startb_x = b.b_x;
    int startb_y = b.b_y;
    int startr_x = b.r_x;
    int startr_y = b.r_y;

    while (v[b.b_x + dx[i]][b.b_y + dy[i]] != '#')
    // 다음 좌표가 벽이 아니라면
    {
        b.b_x += dx[i];
        b.b_y += dy[i];
        if (v[b.b_x][b.b_y] == 'O') break;
        // 이동된 좌표가 구멍이라면 멈춤
    }
    while (v[b.r_x + dx[i]][b.r_y + dy[i]] != '#')
    // 다음 좌표가 벽이 아니라면
    {
        b.r_x += dx[i];
        b.r_y += dy[i];
        if (v[b.r_x][b.r_y] == 'O') break;
        // 이동된 좌표가 구멍이라면 멈춤
    }
    if (b.b_x == b.r_x && b.b_y == b.r_y)
    // 두 구슬의 좌표가 같을 때
    {
        if (v[b.b_x][b.b_y] == 'O')
        // 구슬이 구멍에 들어갔다면
        {
            b.b_x = -1;
            // 파란 공의 좌표를 -1로 바꿔준다. (BFS 함수에서 b_x값이 -1이면 검사하지 않도록 지정)
            return b;
        }
        else
        {
        // 구슬의 좌표가 같지만 구멍에 들어가지 않았다면
            if (i == 0) startb_x < startr_x ? b.r_x++ : b.b_x++;
            // 위쪽 방향으로 굴린 경우) 파란 구슬이 더 위쪽인가 ? 빨간 구슬을 한 칸 아래로 : 파란 구슬을 한 칸 아래로
            else if (i == 1) startb_x < startr_x ? b.b_x-- : b.r_x--;
            // 아래쪽 방향으로 굴린 경우) 파란 구슬이 더 위쪽인가 ? 파란 구슬을 한 칸 위로 : 빨간 구슬을 한 칸 위로
            else if (i == 2) startb_y < startr_y ? b.r_y++ : b.b_y++;
            // 왼쪽 방향으로 굴린 경우) 파란 구슬이 더 왼쪽인가 ? 빨간 구슬을 오른쪽으로 : 파란 구슬을 오른쪽으로
            else startb_y < startr_y ? b.b_y-- : b.r_y--;
            // 오른쪽 방향으로 굴린 경우) 파란 구슬이 더 왼쪽인가 ? 파란 구슬을 왼쪽으로 : 빨간 구슬을 왼쪽으로
        }
    }
    else
    // 두 구슬의 좌표가 같지 않을 때
    {
        if (v[b.b_x][b.b_y] == 'O')
        // 파란 공이 구멍에 들어갔다면
        {
            b.b_x = -1;
            // 파란 공의 좌표를 -1로 바꿔준다
            return b;
        }
    }
    return b;
}

void bfs()
{
    queue<ball_Status> q;
    visit[init.b_x][init.b_y][init.r_x][init.r_y] = true;
    // 처음 시작 위치의 방문 정보를 true로 변경
    q.push(init);
    while (!q.empty())
    {
        ball_Status node = q.front();
        q.pop();
        if (v[node.r_x][node.r_y] == 'O')
        {
            if (node.move > 10) ans = -1;
            // move의 횟수가 10번을 넘어가면 ans에 -1을 대입
            else ans = node.move;
            // 그렇지 않다면 move횟수를 대입
            return;
        }

        for (int i = 0; i < 4; i++)
        {
            ball_Status tmp = move_Towards(i, node);
            if (tmp.b_x == -1)
            {
                continue;
            }
            if (!visit[tmp.b_x][tmp.b_y][tmp.r_x][tmp.r_y])
            {
                visit[tmp.b_x][tmp.b_y][tmp.r_x][tmp.r_y] = true;
                tmp.move++;
                // 방문 정보가 없다면 move의 횟수를 늘려준다
                q.push(tmp);
            }
        }
    }
}

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

    cin >> n >> m;
    v.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> v[i][j];
            if (v[i][j] == 'R' || v[i][j] == 'B')
            {
                v[i][j] == 'R' ? init.input_Red(i, j) : init.input_Blue(i, j);
                // 구조체에 Red와 Blue 위치를 저장
                v[i][j] = '.';
            }
        }
    }
    bfs();
    cout << ans;
}