BOJ 2251 · 물통

알고리즘 분류 : BFS  

부어서 만들 수 있는 물통의 경우의 수를 모두 만들고, 첫 번째 물통이 비어 있을 때 세 번째 물통에 담겨있는 물의 양을 구해야 한다. BFS를 통해 물을 옮기면서 경우의 수를 만들 수 있다.

• 물통이 총 3개이지만, 2개로 해결할 수 있다.
• 물통에서 물을 옮길 때, 물의 양은 변하지 않으므로, 물통의 상태 변화를 첫 번째 물통과 두 번째 물통만 나타내도 된다.
• 세 번째 물통에 있는 물의 양은 C-X-Y로 나타낼 수 있다.
• 물 옮기는 방법은 총 6가지이다. X→Y, X→Z, Y→X, Y→Z, Z→X, Z→Y이다.
• 첫 번째 물통이 비어있으면, 정답 리스트에 세 번째 물통에 남아있는 물의 양을 저장한다.
• 탐색이 끝나면, 정답 리스트를 정렬하고 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct bottle {
    int x, y;
};
int a, b, c;
bool check[201][201];
queue<bottle> q;
vector<int> v;

void pour(int x, int y) {
    if (!check[x][y]) {
        check[x][y] = true;
        q.push({x, y});
    }
}

void bfs() {
    q.push({0, 0});
    check[0][0] = true;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, z = c-x-y; q.pop();
        if (!x) v.push_back(z);
        // x -> y
        int water = min(x, b-y);
        pour(x-water, y+water);
        // x -> z
        water = min(x, c-z);
        pour(x-water, y);
        // y -> x
        water = min(y, a-x);
        pour(x+water, y-water);
        // y -> z
        water = min(y, c-z);
        pour(x, y-water);
        // z -> x
        water = min(z, a-x);
        pour(x+water, y);
        // z -> y
        water = min(z, b-y);
        pour(x, y+water);
    }
}

int main() {
    scanf("%d %d %d", &a, &b, &c);
    bfs();
    sort(v.begin(), v.end());
    for (auto k : v) printf("%d ", k);
    printf("\n");
    return 0;
}

---

Python 3 소스코드

from collections import deque

def pour(x, y):
    if not check[x][y]:
        check[x][y] = True
        q.append((x, y))

def bfs():
    q.append((0, 0))
    check[0][0] = True
    while q:
        x, y = q.popleft()
        z = c-x-y
        if not x:
            v.append(z)
        water = min(x, b-y)
        pour(x-water, y+water)
        water = min(x, c-z)
        pour(x-water, y)
        water = min(y, a-x)
        pour(x+water, y-water)
        water = min(y, c-z)
        pour(x, y-water)
        water = min(z, a-x)
        pour(x+water, y)
        water = min(z, b-y)
        pour(x, y+water)

q = deque()
v = []
a, b, c = map(int, input().split())
check = [[False]*(b+1) for _ in range(a+1)]
bfs()
print(' '.join(map(str, sorted(v))))

---

참고

• 백준 온라인 저지 : BOJ 2251