[ 백준 12886 ] 돌 그룹 (C++)

백준의 돌그룹(12886) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 3개의 돌 그룹 중에서, 2개의 그룹을 골라, 더 큰 쪽의 돌그룹에서 더 작은 쪽의 돌그룹으로 작은쪽 돌그룹의 돌 갯

   수 만큼 준다고 했을 때, 3개의 돌 그룹의 갯수가 모두 같아지는 경우를 찾아야 하는 문제이다.

   BFS를 통해서 구현할 수 있으며, Queue에서는 3개의 돌그룹에 담겨져 있는 돌의 갯수를 관리해 주었다.

2) Queue 반복문 안에서는 모든 조건에 대해 참일 경우 모든 경우에 대해서 다 해보면 된다.

   예를 들어서, A B C 3개의 돌그룹이 있다고 생각해보자.

   BFS의 반복문 안에서는

   1. A < B 인 경우

   2. B < A 인 경우

   3. A < C 인 경우

   4. C < A 인 경우

   5. B < C 인 경우

   6. C < B 인 경우

   이렇게 6개의 경우에 대해서 문제에서 돌의 갯수를 옮겨주라는 대로 옮겨주면 된다. 이 부분은 어렵지 않다.

3) 사실상 이 문제의 어려운 부분은 메모리초과 혹은 시간초과라고 생각한다. 실제로 본인은 이 문제를 풀면서 메모리초과

   시간초과 다떴었다... 3개의 돌그룹에서 중복을 관리하는 부분이 조금 애매하다고 생각한다.

   본인은 처음에 중복을 체크하지 않고, 위의 6개의 조건문만 계속 돌리면서 돌을 옮겨주는 식으로 구현하였는데

   이 때는 메모리초과가 났었다. 또한 시간이 너무 오래걸릴 것 같아서, 임의로 step을 만들어서 Queue의 반복문이

   2000번 이상 돌지 못하게 구현해 보았다. 이 경우에는 시간도 빨리 해결되고 정답 처리를 받을 수 있었지만, 사실상

   이 문제에 대한 테스트케이스가 운이 좋게 2000번 넘는 것이 없어서 정답을 받았을 뿐, 이 문제에 대한 정확한 정답이라고

   생각하지 않았다. 아 물론, 일반적으로 사용하는 Visiti[][][] 3차원 배열을 이용해서 중복 체크를 하려고 했으나, 돌의 갯수

   가 너무 커서 배열로는 감당하기 힘든 크기라서 할 수 없었다.

   그래서 본인은 set을 사용하였다. 3개의 변수를 set으로 관리해주었고, 중복된 조합에 대해서는 Queue에 넣지 않도록

   체크해 주었더니, 정답처리를 받았으나, 메모리와 시간을 엄청나게 받았다.

   이 부분에 대해서는 본인도 정확한 풀이를 잘 모르겠다....

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<set>
 
typedef long long ll;
#define endl "\n"
#define MAX 500 + 1
using namespace std;
 
ll A, B, C;
set<pair<pair<ll, ll>, ll>> Visit;
 
void Input()
{
    cin >> A >> B >> C;
}
 
void Solution()
{
    bool Can_Answer = false;
    queue<pair<pair<ll, ll>, ll>> Q;
    Q.push(make_pair(make_pair(A, B), C));
    Visit.insert(make_pair(make_pair(A, B), C));
 
    while (Q.empty() == 0)
    {
        ll a = Q.front().first.first;
        ll b = Q.front().first.second;
        ll c = Q.front().second;
        Q.pop();
 
        if (a == b && b == c && a == c)
        {
            Can_Answer = true;
            break;
        }
 
        ll Tmp_A, Tmp_B, Tmp_C;
 
        if (a < b)
        {
            Tmp_B = b - a;
            Tmp_A = a + a;
            Tmp_C = c;
            if (Visit.find(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
                Q.push(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
            }
        }
 
        if (a > b)
        {
            Tmp_A = a - b;
            Tmp_B = b + b;
            Tmp_C = c;
            if (Visit.find(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
                Q.push(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
            }
        }
 
        if (a < c)
        {
            Tmp_C = c - a;
            Tmp_A = a + a;
            Tmp_B = b;
            if (Visit.find(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
                Q.push(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
            }
        }
 
        if (a > c)
        {
            Tmp_A = a - c;
            Tmp_C = c + c;
            Tmp_B = b;
            if (Visit.find(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
                Q.push(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
            }
        }
 
        if (b < c)
        {
            Tmp_C = c - b;
            Tmp_B = b + b;
            Tmp_A = a;
            if (Visit.find(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
                Q.push(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
            }
        }
 
        if (b > c)
        {
            Tmp_B = b - c;
            Tmp_C = c + c;
            Tmp_A = a;
            if (Visit.find(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
                Q.push(make_pair(make_pair(Tmp_A, Tmp_B), Tmp_C));
            }
        }
    }    
 
    if (Can_Answer == true) cout << 1 << endl;
    else cout << 0 << 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;
}