[BOJ 2251] 물통

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

2251번: 물통

Tag : bfs, implementation

 

문제요약

물통 A, B, C가 있고 초기에는 C물통만 가득찬 상태다. 

물통의 물을 다른 물통으로 옮길 때는 한 물통이 비거나, 다른 물통이 가득찰 때까지 물을 붓는다.

이때 A는 비우고 C에 담을 수 있는 물의 양을 모두 구하라.

 

풀이

상태가 많아봤자 \(200^3\)개이고 전이를 \(O(1)\)에 할 수 있기 때문에 bfs를 돌리면 된다.

사실 물의 총 용량이 200이기 때문에 실제 정점의 개수는 3H200으로 대략 \(200^2\)개밖에 안된다.

* 구현이 개같다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

int A, B, C;
int cnt[202];
int chk[202][202][202];
vector<int> v;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> A >> B >> C;
    chk[0][0][C] = 1;
    queue<tuple<int, int, int>> q;
    q.push({0, 0, C});
    chk[0][0][C] = 1;
    while(q.size()) {
        auto [a, b, c] = q.front(); q.pop();
//        cout << a <<  ' ' << b << " " << c << ' ' << chk[a][b][c] << endl;
        int na = a, nb = b, nc = c;
        nc = min(C, b + c);
        nb -= nc - c; // b -> c
        na = a;
        if(chk[na][nb][nc] == 0) {
            chk[na][nb][nc] = 1;
            q.push({na, nb, nc});
        }
        na = a, nb = b, nc = c;
        nc = min(C, a + c); // a -> c
        na -= nc - c;
        nb = b;
        if(chk[na][nb][nc] == 0) {
            chk[na][nb][nc] = 1;
            q.push({na, nb, nc});
        }
        na = a, nb = b, nc = c;
        nb = min(B, b + a); // a -> b
        na -= nb - b;
        nc = c;
        if(chk[na][nb][nc] == 0) {
            chk[na][nb][nc] = 1;
            q.push({na, nb, nc});
        }
        na = a, nb = b, nc = c;
        nb = min(B, b + c); // c -> b
        nc -= nb - b;
        na = a;
        if(chk[na][nb][nc] == 0) {
            chk[na][nb][nc] = 1;
            q.push({na, nb, nc});
        }
        na = a, nb = b, nc = c;
        na = min(A, a + c); // c -> a
        nb = b;
        nc -= na - a;
        if(chk[na][nb][nc] == 0) {
            chk[na][nb][nc] = 1;
            q.push({na, nb, nc});
        }
        na = a, nb = b, nc = c;
        na = min(A, a + b); // b -> a
        nb -= na - a;
        nc = c;
        if(chk[na][nb][nc] == 0) {
            chk[na][nb][nc] = 1;
            q.push({na, nb, nc});
        }
    }
    for(int i=0; i<=200; i++) for(int j=0; j<=200; j++) {
        if(chk[0][i][j] == 0) continue;
        if(cnt[j]++ == 0) v.push_back(j);
    }
    sort(v.begin(), v.end());
    for(auto &i : v) cout << i << ' ';
}