[틀림] 백준 14867 물통 // map bfs

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

*시도1

dfs로 6가지 경우의수 탐색 -> 계속 fill A 만 호출되다 스택 오버플로우

* 풀이

가중치가 같은 최단거리는 ? bfs! 처음 찾은게 최단거리 보장

but, 상태 : [a의 물][b의물] = [10만][10만] -> 메모리 초과

상태관찰 -> 상태가 띄엄띄엄 있음 -> 즉, vis를 전부사용하지 않아도됨 -> map을 vis로 활용

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int a,b,c,d,ret=-1;
map<pair<int,int>,int> vis;

struct A {
    int q,w,cnt;
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>a>>b>>c>>d;

    // dfs(0,0,0);
    queue<A> qe;
    qe.push({0,0,0});

    while(qe.size()) {
        auto cur = qe.front(); qe.pop();
        int q = cur.q;
        int w = cur.w;
        int cnt = cur.cnt;

        if(vis[{q,w}]) continue;
        
        if(q==c && w==d) {
            ret=cnt;
            break;
        }
        
        vis[{q,w}]=1;
        qe.push({a,w,cnt+1});
        qe.push({q,b,cnt+1});
        qe.push({0,w,cnt+1});
        qe.push({q,0,cnt+1});
        int _q=q; //원본
        int _w=w; 
        // q->w
        int gab = b-w;
        //w에 빈공간이있으면
        if(gab) {
            if(q >= gab) {
                w=b;
                q -=gab;
            }
            else {
                w+=q;
                q=0;
            }
        }
        qe.push({q,w,cnt+1});

        //원복
        q=_q;
        w=_w;
        // w->q
        int gab2 = a-q;
        //w에 빈공간이있으면
        if(gab2) {
            if(w >= gab2) {
                q=a;
                w -=gab2;
            }
            else {
                q+=w;
                w=0;
            }
        }
        qe.push({q,w,cnt+1});
    }
    
    
    cout<<ret;
   
    return 0;
}

수학부분 개선

enqueue(min(x + y, a), max(0, x + y - a), m[{x, y}]);
enqueue(max(0, x + y - b), min(x + y, b), m[{x, y}]);