백준 2251 물통

한 번에 한 통을 붓기 때문에 가중치가 1이다. 또한 visit 배열을 만든다고 할 때 200*200*200 = 8000000이므로 시간안에 풀 수 있는 문제이다.

bfs로 풀 수 있다. a에 들어 있는 물의 양이 0일 때는 queue에 다시 넣지 않고 답을 저장하는 vector에 넣을 것이고, 한 번 만들어진 경우는 visit 함수를 이용하여 다시 queue에 넣지 않을 것이므로 queue는 empty가 될 수밖에 없다.

 

푸는 방법은 어렵지 않지만, 경우의 수를 다 나누어 주는 것이 복잡하다.

코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
 
bool visit[200][200][200];
 
 
 
int main(int argc, char** argv) {
    int a, b, c;
    cin >> a >> b >> c;
 
    vector<int> v;
    queue<tuple<int, int, int>> q;
    q.push(make_tuple(0, 0, c));
 
    while (!q.empty()) {
        int x, y, z;
        tie(x, y, z) = q.front();
        q.pop();
 
        if (x == 0) {
            visit[x][y][z] = true;
            v.push_back(z);
        }
 
        if (x != 0) {
            if (b - y < x) {
                if (!visit[x - (b - y)][b][z]) {
                    visit[x - (b - y)][b][z] = true;
                    q.push(make_tuple(x - (b - y), b, z));
                }
            }
            if (b - y >= x) {
                if (!visit[0][x + y][z]) {
                    visit[0][x + y][z] = true;
                    q.push(make_tuple(0, x + y, z));
                }
            }
            if (c - z < x) {
                if (!visit[x - (c - z)][y][c]) {
                    visit[x - (c - z)][y][c] = true;
                    q.push(make_tuple(x - (c - z), y, c));
                }
            }
            if (c - z >= x) {
                if (!visit[0][y][x + z]) {
                    visit[0][y][x + z] = true;
                    q.push(make_tuple(0, y, x + z));
                }
            }
        }
        if (y != 0) {
            if (a - x < y) {
                if (!visit[a][y - (a - x)][z]) {
                    visit[a][y - (a - x)][z] = true;
                    q.push(make_tuple(a, y - (a - x), z));
                }
            }
            if (a - x >= y) {
                if (!visit[x + y][0][z]) {
                    visit[x + y][0][z] = true;
                    q.push(make_tuple(x + y, 0, z));
                }
            }
            if (c - z < y) {
                if (!visit[x][y - (c - z)][c]) {
                    visit[x][y - (c - z)][c] = true;
                    q.push(make_tuple(x, y - (c - z), c));
                }
            }
            if (c - z >= y) {
                if (!visit[x][0][y+z]) {
                    visit[x][0][y+z] = true;
                    q.push(make_tuple(x, 0, y+z));
                }
            }
        }
        if (z != 0) {
            if (a - x < z) {
                if (!visit[a][y][z - (a - x)]) {
                    visit[a][y][z - (a - x)] = true;
                    q.push(make_tuple(a, y, z - (a - x)));
                }
            }
            if (a - x >= z) {
                if (!visit[x + z][y][0]) {
                    visit[x + z][y][0] = true;
                    q.push(make_tuple(x + z, y, 0));
                }
            }
            if (b - y < z) {
                if (!visit[x][b][z - (b - y)]) {
                    visit[x][b][z - (b - y)] = true;
                    q.push(make_tuple(x, b, z - (b - y)));
                }
            }
            if (b - y >= z) {
                if (!visit[x][y + z][0]) {
                    visit[x][y + z][0] = true;
                    q.push(make_tuple(x, y + z, 0));
                }
            }
        }
    }
 
    sort(v.begin(), v.end());
    for (auto x : v) {
        printf("%d ", x);
    }
    printf("\n");
 
    return 0;
}