[2251] 물통 (C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
bool visit[201][201][201];

int A, B, C;
vector<int> ans;

void BFS();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> A >> B >> C;

    BFS();

    sort(ans.begin(), ans.end());
    for (int i : ans) cout << i << " ";

    return 0;
}

void BFS() {
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(0, 0), C));

    while (!Q.empty()) {
        int now_a = Q.front().first.first;
        int now_b = Q.front().first.second;
        int now_c = Q.front().second;
        Q.pop();

        if (visit[now_a][now_b][now_c]) continue;
        visit[now_a][now_b][now_c] = true;        

        if (now_a == 0) ans.push_back(now_c);

        // A->B
        if (now_a + now_b > B) Q.push(make_pair(make_pair(now_a + now_b - B, B), now_c));
        else Q.push(make_pair(make_pair(0, now_a + now_b), now_c));

        // A->C
        if (now_a + now_c > C) Q.push(make_pair(make_pair(now_a + now_c - C, now_b), C));
        else Q.push(make_pair(make_pair(0, now_b), now_a + now_c));

        // B->A
        if (now_b + now_a > A) Q.push(make_pair(make_pair(A, now_b + now_a - A), now_c));
        else Q.push(make_pair(make_pair(now_a + now_b, 0), now_c));

        // B->C
        if (now_b + now_c > C) Q.push(make_pair(make_pair(now_a, now_b + now_c - C), C));
        else Q.push(make_pair(make_pair(now_a, 0), now_b + now_c));

        // C->A
        if (now_c + now_a > A) Q.push(make_pair(make_pair(A, now_b), now_c + now_a - A));
        else Q.push(make_pair(make_pair(now_a + now_c, now_b), 0));

        // C->B
        if (now_c + now_b > B) Q.push(make_pair(make_pair(now_a, B), now_c + now_b - B));
        else Q.push(make_pair(make_pair(now_a, now_b + now_c), 0));
    }  
}

 

1. 물통은 A, B, C 3개가 존재하며, 편의상 물통의 용량을 A, B, C로 설정한다

2. 물통에 담긴 현재 물의 양을 now_a, now_b, now_c로 설정한다

3. 3개의 물통에 나눠 담긴 물이 겹치는 경우 방문하지 않기 위해 visit 배열을 선언한다

4. 물이 이동할 수 있는 경우는 A→B, A →C, B→A, B→C, C→A, C→B 총 6가지이다

5. 예를 들어 A→B에서, now_a + now_b > B, now_a + now_ b < B 총 두가지 경우가 존재한다.

=> now_a + now_b > B인 경우 B에는 B만큼의 물을 넣고, A에는 B에 넣고 남은 now_a + now_b - B만큼의 물을 넣는다

now_a + now_b < B인 경우 B에는 기존 now_b에 now_a만큼을 더 넣은 now_b + now_a의 물이 들어가며, A는 0이 된다

6. now_a가 0이 될 때마다 now_c의 값을 ans에 저장한다

7. BFS가 종료되면 ans에 있는 값을 오름차순으로 정렬하고 출력한다

 

 

 

 

---

6가지 경우가 존재, 3개의 물통에 나눠 담긴 물의 경우의 수를 visit으로 체크, now_a가 0일 때 now_c의 값을 ans에 저장

3가지 조건을 생각해내는데에 시간이 많이 걸린 문제였다.

또한 6가지 경우의 각 조건에서 실수하지 않도록 주의가 필요하다.