물통 14867

문제

접근 방법

BFS로 풀면 된다. 빨리 최소 작업 수에 도달하기 위해서는 BFS로 푸는 것이 좋다.

수작업으로 F, E, M에 대한 6개의 경우를 모두 입력할 수도 있지만 중복된 부분은 없애주는 게 나을 거 같아서 배열을 이용하였다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#define bucketCnt 2
using namespace std;
map<pair<int, int>, int> visted;
int abcd[4];
struct node
{
    int bucket[bucketCnt];
};
queue<node> q;
void input(node prevNode, node nextNode)
{
    if (!visted[{nextNode.bucket[0], nextNode.bucket[1]}])
    {
        visted[{nextNode.bucket[0], nextNode.bucket[1]}] = visted[{prevNode.bucket[0], prevNode.bucket[1]}] + 1;
        if (nextNode.bucket[0] == abcd[2] && nextNode.bucket[1] == abcd[3])
        {
            cout << visted[{nextNode.bucket[0], nextNode.bucket[1]}] - 1;
            exit(0);
        }
        q.push(nextNode);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> abcd[0] >> abcd[1] >> abcd[2] >> abcd[3];
    if (!abcd[2] && !abcd[3])
    {
        cout << 0;
        return 0;
    }
    q.push({0, 0});
    visted[{0, 0}] = 1;
    while (!q.empty())
    {
        node cur = q.front();
        q.pop();
        for (int i = 0; i < bucketCnt; ++i)
        {
            node next = {cur.bucket[0], cur.bucket[1]};

            node move = next;
            int j = (i + 1) % bucketCnt;
            move.bucket[j] += move.bucket[i];
            move.bucket[i] = 0;
            if (abcd[j] < move.bucket[j])
            {
                move.bucket[i] = move.bucket[j] - abcd[j];
                move.bucket[j] = abcd[j];
            }
            input(cur, move);

            next.bucket[i] = abcd[i];
            input(cur, next);

            next.bucket[i] = 0;
            input(cur, next);
        }
    }
    cout << -1;
    return 0;
}

풀이

처음에는 배열로 방문 확인을 하였다. 하지만 문제가 있었는데 100,000*100,000만큼의 배열을 만들어야 하기 때문이다.
메모리 제한이 512MB인데 그렇다는 건 512*1024*1024/4만큼의 배열만 가능하다는 것이다.

하지만 100,000*100,000은 그 값을 넘기에 문제가 발생하고 43점을 받았다. 해결하는 법은 map을 사용하는 것이다.
물통의 크기를 전부 사용하는 것이 아니기에 map을 사용해야 하는 것이다. (a와 b가 100,000, 100,000의 크기라면 사실상 0, 100,000만이 사용된다는 점에서 map의 필요성을 알 수 있다)