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

문제

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

13460번: 구슬 탈출 2

 

 

풀이

십자 방향으로 구슬을 움직이며 도착지점까지의 최단거리를 찾는 문제입니다.

최단거리를 찾는 문제이므로 bfs 탐색을 통해 물제를 해결해 보겠습니다.

 

구현 문제와 살짝 짬뽕되어 문제의 조건도 많고 구현과정도 길어지지만 큰 알고리즘은 bfs 탐색으로 하나씩 정리해나가면 이해할 수 있습니다.

 

먼저 bfs 탐색 종료 조건부터 알아봅시다.

종료조건 1 - 구슬 이동 횟수 10회 초과

        if (curCnt > 10)
        {
            answer = -1;
            break;
        }

10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력합니다.

 

종료조건 2 - 빨간 구슬 탈출

        if (curRed == goal && curBlue != goal)
        {
            answer = curCnt;
            break;
        }

빨간구슬이 구멍에 위치하고, 파란구슬은 구멍에 위치하지 않을경우 bfs 탐색을 종료하고 움직인 횟수를 출력합니다.

 

 

 

다음으로는 구슬의 움직임에 대해 구현해봅시다.

구슬 움직임

        while (true)
        {
            if (board[nRed.x][nRed.y] == '#')
            {
                nRed = nRed - d;
                break;
            }

            if (nRed == goal)
                break;

            nRed = nRed + d;
            ++redMove;
        }

한칸씩 d 방향(상, 하, 좌, 우 중 하나)으로 이동합니다. 이때 벽을 만나기 전까지 이동합니다. 혹은 구멍을 만난다면 더 이상 움직이지 않습니다.

움직일 때마다 움직인 횟수를 세어줍니다. 이 움직인 횟수는 바로 다음에서 활용됩니다.

 

 

구슬 겹침 분리

구슬은 구멍이 아니라면 같은 칸에 두 개가 동시에 위치할 수 없습니다. 그래서 이동 후 두 구슬의 위치가 같다면 분리해주어야 합니다.

        if (nRed != goal && nRed == nBlue)
        {
            if (blueMove > redMove)
                nBlue = nBlue - d;
            else
                nRed = nRed - d;
        }

같은 방향으로 움직이는데 도착 지점이 같다면 더 많이 움직인 구슬이 더 뒤에서 출발했다는 뜻이 됩니다.

움직인 횟수를 비교해서 더 많이 움직인 구슬을 한 칸 -d 방향으로 움직여 겹침 현상을 해결할 수 있습니다.

 

 

 

중복 제거

마지막으로 이 문제에서 가장 중요하다 생각하는 부분입니다.

bfs 탐색이므로 이미 탐색된 위치에 다시 도착한다는 것은 최단거리가 아니라는 뜻이 됩니다. 그래서 보통 visited 배열을 만들어 중복 탐색을 관리해줍니다.

 

그런데 이번 문제는 구슬이 두 개이므로 더 많은 상황이 발생할 수 있습니다.

빨간 구슬이 같은 위치라도, 파란 구슬의 위치가 다르다면 다른 상황으로 취급해야 합니다.

경우의 수를 빨간 구슬의 (x, y) * 파란 구슬의 (x, y)로 표현할 수 있고, 이는 4차원 visited 배열로 구현할 수 있습니다.

    bool visited[10][10][10][10];
    memset(visited, false, sizeof(visited));

4차원 배열이라 메모리 초과되지 않을까? 했지만  N, M 이 10을 초과하지 않으므로 메모리에 부담없습니다.

 

 

 

 

코드

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

using namespace std;

struct Pos
{
    int x;
    int y;

    bool operator==(Pos input)
    {
        return x == input.x && y == input.y;
    }
    bool operator!=(Pos input)
    {
        return !(x == input.x && y == input.y);
    }
    Pos operator+(Pos input)
    {
        Pos ret;
        ret.x = x + input.x;
        ret.y = y + input.y;
        return ret;
    }
    Pos operator-(Pos input)
    {
        Pos ret;
        ret.x = x - input.x;
        ret.y = y - input.y;
        return ret;
    }
};

int n, m;
vector<vector<char>> board;
vector<Pos> dir { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
Pos red;
Pos blue;
Pos goal;

void Input()
{
    cin >> n >> m;
    board.resize(n, vector<char>(m));
    for (int i=0; i<n; ++i)
    {
        string line;
        cin >> line;
        for (int j=0; j<m; ++j)
        {
            board[i][j] = line[j];

            switch(line[j])
            {
                case 'R':
                    red = {i, j};
                    break;
                case 'B':
                    blue = {i, j};
                    break;
                case 'O':
                    goal = {i, j};
                    break;
                default:
                    break;
            }
        }
    }
}

int bfs()
{
    struct Params
    {
        Pos r;
        Pos b;
        int cnt;
    };

    queue<Params> q;
    q.push({red, blue, 0});
    int answer = -1;
    bool visited[10][10][10][10];
    memset(visited, false, sizeof(visited));

    while(!q.empty())
    {
        Pos curRed = q.front().r;
        Pos curBlue = q.front().b;
        int curCnt = q.front().cnt;
        q.pop();

        if (curCnt > 10)
        {
            answer = -1;
            break;
        }

        if (curRed == goal && curBlue != goal)
        {
            answer = curCnt;
            break;
        }

        for (auto d : dir)
        {
            Pos nRed = curRed;
            Pos nBlue = curBlue;
            int redMove = 0;
            int blueMove = 0;
            
            while (true)
            {
                if (board[nRed.x][nRed.y] == '#')
                {
                    nRed = nRed - d;
                    break;
                }

                if (nRed == goal)
                    break;

                nRed = nRed + d;
                ++redMove;
            }

            while (true)
            {
                if (board[nBlue.x][nBlue.y] == '#')
                {
                    nBlue = nBlue - d;
                    break;
                }

                if (nBlue == goal)
                    break;

                nBlue = nBlue + d;
                ++blueMove;
            }

            if (blueMove == 0 && redMove == 0)
                continue;


            if (nRed != goal && nRed == nBlue) // 현재 위치가 구멍이라면 두 구슬이 같은 위치일 수 있음
            {
                if (blueMove > redMove)
                    nBlue = nBlue - d;
                else
                    nRed = nRed - d;
            }


            if (visited[nBlue.x][nBlue.y][nRed.x][nRed.y])
                continue;

            visited[nBlue.x][nBlue.y][nRed.x][nRed.y] = true;

            q.push({nRed, nBlue, curCnt+1});
        }
    }

    return answer;
}

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

    Input();

    cout << bfs() << endl;
    return 0;
}