물통

코드

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#include <stack>
#define ull unsigned long long
using namespace std;
map<int,bool> m;
vector<int> ans;
int w_capacity[4];
bool vis[201][201][201]; // vis[w1][w2][w3] -> w1,w2,w3 상태
struct water{
    int pos;
    int content;
};
void move(water& from , water& to){
    int left = w_capacity[to.pos] - to.content;
    int put = from.content;
    if(left >= put){ // 공간이 더 크면
        to.content += put;
        from.content = 0;
    }else{ // 공간이 더 작으면
        to.content += left;
        from.content -= left;
    }
}
void DFS(water arr[4]){
    if(arr[1].content == 0 and !m[arr[3].content]){
        m[arr[3].content] = true;
        ans.push_back(arr[3].content);
    }
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            if(i == j) continue;
            water tmp[4];
            for(int i=1;i<=3;i++) tmp[i] = arr[i];
            move(tmp[i], tmp[j]);
            if(vis[tmp[1].content][tmp[2].content][tmp[3].content]) continue;
            vis[tmp[1].content][tmp[2].content][tmp[3].content] = true;
            DFS(tmp);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> w_capacity[1] >> w_capacity[2] >> w_capacity[3];
    water t0 = {0, 0}; // 자리 채우기 용
    water t1 = {1, 0};
    water t2 = {2, 0};
    water t3 = {3, w_capacity[3]};
    water tmp[4] = {t0, t1, t2, t3};
    DFS(tmp);
    sort(ans.begin(), ans.end());
    for(auto a : ans)
        cout << a << ' ';
    return 0;
}

• 느낀 점
  • DFS로 모든 물병간 옮기는 경우의 수를 수행해서 구해야겠다고 생각
  • 최초 3차원 vis를 vis[water][content][from][to]로 생각해서 오답이 나옴
    (from에서 to로 water을 줘서 content가 되었다 : 지금생각해보니 매우 복잡하게 한 것 같다, 게다가 오답)
    --> vis[w1.content][w2.content][w3.content]로 두어야 문제 해결이 가능
            : 각 물병의 상태에 따라 vis배열을 구성!

• BFS 풀이 --> queue에 w1,w2,w3 정보를 유지하면서 수행 + vis[w1][w2][w3] 사용