[BOJ/백준][Gold2] 14867 : 물통 (C++)

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

14867번: 물통

 

 

[난이도] Gold2
[유형] BFS

[풀이]
모든 경우에 6가지 물통간 이동이 가능하다. 6^k 개씩 계속 경우가 늘어날 것 같지만
(p,q)를 현재 A,B 물통의 물의 양이라고 했을 때, (p,q)의 경우의 수가 몇개 나오지 않는다고 한다.
(정확한 증명은 어렵지만 물을 전체 다넣거나, 전체 다빼거나, 전체 다옮기거나 하는 단순한 연산들만 반복해서 그렇게 되는 것 같다.)

BFS인 것을 눈치채도 A,B가 최대 100000까지 나오므로 배열로는 메모리 초과를 당하게 된다.

그러므로 set memo[100001]; 와 같이 set을 이용해야 한다.
(1,3)이라면 mem[1].insert(3) 과 같이 저장할 수 있다.
이후 풀이는 일반 BFS와 동일하다.

 

#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
int cap[2],tar[2];
set<int> memo[100001];
queue<pair<int,int>> q;
int main(){
    scanf("%d%d%d%d",&cap[0],&cap[1],&tar[0],&tar[1]);

    q.push({0,0});
    memo[0].insert(0);
    int ret=0;
    while(!q.empty()){

        int sz=q.size();
        while(sz--){
            auto qf = q.front(); q.pop();
            int v[2];
            v[0]=qf.first, v[1]=qf.second;
            if(v[0]==tar[0] && v[1]==tar[1]){
                printf("%d",ret);
                return 0;
            }
            for(int i=0;i<6;i++){
                int a,b;
                if(i==0) a=cap[0],b=v[1];
                else if(i==1) a=v[0],b=cap[1];
                else if(i==2) a=0,b=v[1];
                else if(i==3) a=v[0],b=0;
                else if(i==4) a=min(cap[0],v[0]+v[1]), b=v[1]-min(cap[0]-v[0],v[1]);
                else a=v[0]-min(cap[1]-v[1],v[0]),b=min(cap[1],v[1]+v[0]);

                if(memo[a].find(b) == memo[a].end()){
                    memo[a].insert(b);
                    q.push({a,b});
                }
            }
        }
        ret++;
    }
    puts("-1");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/14867.cpp