백준 14867 물통

출처: https://www.acmicpc.net/problem/14867 

A 물통과 B 물통에 든 물의 양에 대한 2차원 배열을 만들어서 visit check하며 bfs로 풀면 되지만 그럼 10만x10만이 된다. 

그런데 점화식을 써보면, 두 물통에 담긴 물의 양 중 하나는 반드시 0이나 full이라는 사실을 알 수 있다. 

(a,b) -> (full,b) (a,full) (0,b) (a,0) / (a+b,0) or (full,나머지) / (0,a+b) or (나머지, full) 

그래서 2차원 배열의 테두리만 필요하므로 공간복잡도는 문제없다.

 

#include <iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef struct a
{
    int p;
    int q;
    int ct;
} type;
int A,B,a,b,x,y;
int aempty[100005];
int afull[100005];
int bempty[100005];
int bfull[100005];
int gcd(int a,int b)
{
    if(a<b)
    {
        int tmp=a;
        a=b;
        b=tmp;
    }
    while(b!=0)
    {
        int n=a%b;
        a=b;
        b=n;
    }
    return a;
}
queue<type> Q;
bool check(int a,int b,int ct)
{
    int flag=0;
    if(a==0&&aempty[b]==0)
    {
        flag=1;
        aempty[b]=ct;
    }
    if(a==A&&afull[b]==0)
    {
        flag=1;
        afull[b]=ct;
    }
    if(b==0&&bempty[a]==0)
    {
        flag=1;
        bempty[a]=ct;
    }
    if(b==B&&bfull[a]==0)
    {
        flag=1;
        bfull[a]=ct;
    }
    if(flag) return true;
    else return false;
}
int main()
{
    cin >> A >> B >> x >> y;
    int ans;
    if(x!=0&&x!=A&&y!=0&&y!=B)
    {
        cout << -1 ;
        return 0;
    }
    int k=gcd(A,B);
    A/=k;
    B/=k;
    if(x%k!=0||y%k!=0)
    {
        cout << -1;
        return 0;
    }
    if(x!=0) x/=k;
    if(y!=0) y/=k;
    Q.push({0,0,0});
    while(!Q.empty())
    {
        type now=Q.front();
        int p=now.p, q=now.q, ct=now.ct;
        Q.pop();
        if(p==x&&q==y)
        {
            if(p==0) ans=aempty[q];
            if(p==A) ans=afull[q];
            if(q==0) ans=bempty[p];
            if(q==B) ans=bfull[p];
            break;
        }
        if(check(A,q,ct+1)) Q.push({A,q,ct+1});
        if(q!=0&&check(0,q,ct+1)) Q.push({0,q,ct+1});
        if(check(p,B,ct+1)) Q.push({p,B,ct+1});
        if(p!=0&&check(p,0,ct+1)) Q.push({p,0,ct+1});
        if(B>=p+q)
        {
            if((p+q)!=0&&check(0,p+q,ct+1)) Q.push({0,p+q,ct+1});
        }
        else
        {
            if((p+q)!=0&&check((p+q)-B,B,ct+1)) Q.push({(p+q)-B,B,ct+1});
        }
        if(A>=p+q)
        {
            if((p+q)!=0&&check(p+q,0,ct+1)) Q.push({p+q,0,ct+1});
        }
        else
        {
            if((p+q)!=0&&check(A,(p+q)-A,ct+1)) Q.push({A,(p+q)-A,ct+1});
        }
    }
    cout <<ans;
}