[백준] 2251번 물통

문제

https://www.acmicpc.net/problem/2251

풀이과정

A, B, C 세 가지 물통의 부피가 주어진다. 문제에서 물통 C는 처음부터 꽉 차있다고 주어진다. 문제에서 원하는 답은 물통 A가 비어있을 때 C에 남아있는 물의 양이다. 문제에서 물이 옮겨담기는 과정에서 손실되는 경우는 없다고 했다. 그러므로 A, B 물통에 남아있는 물의 양만 있다면 물통 C에 남아있는 물의 양도 구할 수 있다.

c(물통 C의 남은 물의 양) = C(물통 C의 부피) - a(물통 A의 남은 물의 양) - b(물통 B의 남은 물의 양)

물을 옮겨담는 경우의 수는 총 6가지다.

1. A -> B
2. A -> C
3. B -> A
4. B -> C
5. C -> A
6. C -> B

모든 경우를 탐색해보기 위해 BFS를 이용하고 물통 A, B의 남은 물의 양만을 이용해 진행한다.

소스코드

#include <iostream>
#include <queue>

using namespace std;

#define MAX 201

bool chk[MAX][MAX];
bool ans[MAX];
int A, B, C;

void push_ans(queue<pair<int,int>> &q,int x, int y,int z)
{
    if (chk[x][y] == false)
    {
        chk[x][y] = true;
        q.push(make_pair(x, y));
        // 물통 A가 비어있는 경우 물통 C의 남아있는 물의 양
        if (x == 0)
        {
            ans[z] = true;
        }
    }
}

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

    cin >> A >> B >> C;

    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    chk[0][0] = true;
    ans[C] = true;

    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        int z = C - x - y;
        q.pop();

        int nx, ny, nz;

        nx = x; ny = y; nz = z;

        // x -> y
        ny += nx; nx = 0;
        if (ny >= B)
        {
            nx = ny - B;
            ny = B;
        }

        push_ans(q, nx, ny, nz);

        nx = x; ny = y; nz = z;
        // x -> z;
        nz += nx; nx = 0;
        if (nz >= C)
        {
            nx = nz - C;
            nz = C;
        }

        push_ans(q, nx, ny, nz);

        nx = x; ny = y; nz = z;
        // y -> x
        nx += ny;  ny = 0;
        if (nx >= A)
        {
            ny = nx - A;
            nx = A;
        }

        push_ans(q,nx, ny, nz);
        nx = x; ny = y; nz = z;
        // y -> z
        nz += ny; ny = 0;
        if (nz >= C)
        {
            ny = nz - C;
            nz = C;
        }
        push_ans(q, nx, ny, nz);
        nx = x; ny = y; nz = z;
        // z -> x 
        nx += nz; nz = 0;
        if (nx >= A)
        {
            nz = nx - A;
            nx = A;
        }
        push_ans(q, nx, ny, nz);
        nx = x; ny = y; nz = z;

        // z -> y
        ny += nz; nz = 0;
        if (ny >= B)
        {
            nz = ny - B;
            ny = B;
        }
        push_ans(q, nx, ny, nz);
    }

    for (int i = 0; i < MAX; i++)
    {
        if (ans[i])
            cout << i << " ";
    }

    cout << "\n";

    return 0;
}