BOJ 14867 물통

물통

(http://boj.kr/14867)

물을 A에서 B로 옮기던지, B에서 A에서 옮기던지 상관 없이 옮긴 후의 상태는 4가지가 된다.

1. A가 비어있음

2. A가 가득참

3. B가 비어있음

4. B가 가득참

그렇기 때문에 모든 경우를 확인해도 2A+2B가지의 경우밖에 없기 때문에 시간초과가 나지 않는다.

다른 방법은, A에서 B로 물을 옮기고, 그 후에 B에서 A로 물을 옮기는 것은 최단의 방법일 가능성이 없다.

마찬가지로 B에서 A로 물을 옮긴 후 A에서 B로 물을 옮기는 것도 가능성이 없다.

A에서 B로 물을 옮기는 것을 기준으로 하면, A가 비었다면 물을 채우고, B가 가득 찼다면 물을 버리고, 그렇지 않다면 물을 옮기는 식으로 찾아가면 빠르게 구할 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
bool c1[100001], c2[100001], c3[100001], c4[100001];
 
int main() {
    int a, b, c, d;
    queue<vector<int> > q;
 
    scanf("%d %d %d %d", &a, &b, &c, &d);
 
    q.push({ 0, 0, 0 });
    c1[0] = true;
    c3[0] = true;
 
    while (!q.empty()) {
        vector<int> now = q.front();
        q.pop();
 
        if (now[0] == c && now[1] == d) {
            printf("%d", now[2]);
 
            return 0;
        }
 
        if (c2[now[1]] == false) {
            c2[now[1]] = true;
            q.push({ a, now[1], now[2] + 1 });
        }
        if (c4[now[0]] == false) {
            c4[now[0]] = true;
            q.push({ now[0], b, now[2] + 1 });
        }
        if (c1[now[1]] == false) {
            c1[now[1]] = true;
            q.push({ 0, now[1], now[2] + 1 });
        }
        if (c3[now[0]] == false) {
            c3[now[0]] = true;
            q.push({ now[0], 0, now[2] + 1 });
        }
        if (now[0] > b - now[1] && c4[now[0] - b + now[1]] == false) {
            c4[now[0] - b + now[1]] = true;
            q.push({ now[0] - b + now[1], b, now[2] + 1 });
        }
        if (now[0] <= b - now[1] && c1[now[1] + now[0]] == false) {
            c1[now[1] + now[0]] = true;
            q.push({ 0, now[1] + now[0], now[2] + 1 });
        }
        if (now[1] > a - now[0] && c2[now[1] - a + now[0]] == false) {
            c2[now[1] - a + now[0]] = true;
            q.push({ a, now[1] - a + now[0], now[2] + 1 });
        }
        if (now[1] <= a - now[0] && c3[now[0] + now[1]] == false) {
            c3[now[0] + now[1]] = true;
            q.push({ now[0] + now[1], 0, now[2] + 1 });
        }
    }
    printf("-1");
 
    return 0;
}