[ 백준 2251 ] 물통 (C++)

백준의 물통(2251) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 문제를 간략하게 다시 말해보면, A B C 라는 3개의 물통이 있는데 이 물통의 물을 서로서로 옮길수가 있는데,

   옮길 때의 조건으로는 물을 옮기는 쪽의 물통의 물이 0이되거나, 물을 받는 쪽의 물통의 물이 가득 차면

   옮길 수 있을 때, A물통이 0일 때 C물통의 양을 모두 구하라는 것이 문제이다.

   BFS / DFS로 쉽게 풀 수 있는 문제이다. 본인은 BFS로 풀이하였는데, Queue에 3개의 물통의 물 양을 넣어서 관리해주었다.

   중복된 탐색을 피하기 위해서 Visit[][][] 3차원 배열을 사용하였으며,

   Visit[a][b][c] = true의 의미는 A물통에 a의 물양이, B물통에 b의 물양이, C물통에 c의 물양이 들어 있을 때는 이미

   탐색했습니다 라는 의미로 사용하였다.

   물을 어느 물통에서 어느 물통으로 옮길 수 있는지, 물을 옮기고 나면 각각의 물통의 물의 양이 어떻게 변하는지 조금만

   생각한다면 쉽게 풀 수 있는 문제이다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 201
using namespace std;
 
int A, B, C;
bool Visit[MAX][MAX][MAX];
 
vector<int> V;
 
void Input()
{
    cin >> A >> B >> C;
}
 
void Solution()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(0, 0), C));
 
    while (Q.empty() == 0)
    {
        int a = Q.front().first.first;
        int b = Q.front().first.second;
        int c = Q.front().second;
        Q.pop();
 
        if (Visit[a][b][c] == true) continue;
        Visit[a][b][c] = true;
 
        if (a == 0) V.push_back(c);
 
        // A물통에서 B물통으로 줄 때
        if (a + b > B) Q.push(make_pair(make_pair(a + b - B, B), c));
        else Q.push(make_pair(make_pair(0, a + b), c));
 
        // A물통에서 C물통으로 줄 때
        if (a + c > C) Q.push(make_pair(make_pair(a + c - C, b), C));
        else Q.push(make_pair(make_pair(0, b), a + c));
 
        // B물통에서 A물통으로 줄 때
        if (b + a > A) Q.push(make_pair(make_pair(A, b + a - A), c));
        else Q.push(make_pair(make_pair(b + a, 0), c));
 
        // B물통에서 C물통으로 줄 때
        if (b + c > C) Q.push(make_pair(make_pair(a, b + c - C), C));
        else Q.push(make_pair(make_pair(a, 0), b + c));
 
        // C물통에서 A물통으로 줄 때
        if (c + a > A) Q.push(make_pair(make_pair(A, b), c + a - A));
        else Q.push(make_pair(make_pair(c + a, b), 0));
 
        // C물통에서 B물통으로 줄 때
        if (c + b > B) Q.push(make_pair(make_pair(a, B), c + b - B));
        else Q.push(make_pair(make_pair(a, b + c), 0));
    }
 
    sort(V.begin(), V.end());
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i] << " ";
    }
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}