[C++][백준 16197] 두 동전

문제

접근 방법

두 동전을 이동시키면서 밖으로 나가는지 확인하는 것이 목표이다.

각 칸 사이의 거리가 1만큼의 거리이므로 BFS를 사용하더라도 최소 횟수를 구할 수 있다.

코드

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

vector<vector<bool>> board;
int N, M;

struct coin
{
    int y, x;

    const coin operator+(const coin &other) const
    {
        return {y + other.y, x + other.x};
    }

    const bool operator==(const coin &other) const
    {
        return y == other.y && x == other.x;
    }

    const bool operator<(const coin &other) const
    {
        if (other.y == y)
        {
            return x < other.x;
        }
        else
        {
            return y < other.y;
        }
    }

    const bool isOut() const
    {
        return y < 0 || x < 0 || y >= N || x >= M;
    }

    void adjustPos(const coin &d)
    {
        if (board[y][x])
        {
            y -= d.y;
            x -= d.x;
        }
    }
} dir[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

struct node
{
    coin coin1;
    coin coin2;

    const bool operator<(const node other) const
    {
        if (coin1 == other.coin1)
        {
            return coin2 < other.coin2;
        }
        else
        {
            return coin1 < other.coin1;
        }
    }
};

void bfs(coin curCoin1, coin curCoin2)
{
    queue<node> q = queue<node>();
    map<node, int> dist = map<node, int>();

    node start = {curCoin1, curCoin2};
    q.push(start);
    dist[start] = 1;

    while (!q.empty())
    {
        node cur = q.front();
        q.pop();

        for (const coin &d : dir)
        {
            coin nextCoin1 = cur.coin1 + d;
            coin nextCoin2 = cur.coin2 + d;

            if (nextCoin1.isOut() || nextCoin2.isOut())
            {
                if (nextCoin1.isOut() && nextCoin2.isOut())
                {
                    continue;
                }

                if (dist[cur] > 10)
                {
                    break;
                }

                cout << dist[cur];
                return;
            }

            nextCoin1.adjustPos(d);
            nextCoin2.adjustPos(d);

            if (nextCoin1 == nextCoin2)
            {
                continue;
            }

            node next = {nextCoin1, nextCoin2};

            if (dist[next] != 0)
            {
                continue;
            }

            dist[next] = dist[cur] + 1;
            q.push(next);
        }
    }

    cout << -1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> M;

    board = vector<vector<bool>>(N, vector<bool>(M));

    coin coin1 = {-1}, coin2;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            char c;
            cin >> c;

            if (c == '#')
            {
                board[i][j] = true;
            }
            else if (c == 'o')
            {
                coin newCoin{i, j};

                if (coin1.y == -1)
                {
                    coin1 = newCoin;
                }
                else
                {
                    coin2 = newCoin;
                }
            }
        }
    }

    bfs(coin1, coin2);
    return 0;
}

풀이

bfs를 통해 탐색하며 한 개의 동전만 떨어지는 경우를 찾아내면 된다. 두 동전이 겹쳐지는 순간부터는 한 개의 동전만 떨어질 수 없으므로 무시하면 된다.
또한 이미 두 동전과 똑같은 경우를 방문했다면 해당 경우는 최단 거리가 아니므로 무시하면 된다.

모든 경우를 확인해 봤을 때 한 개의 동전만 떨어지는 경우를 못 찾았다면 -1을 출력하여 요구하는 출력을 충족하면 된다.