백준 2251번 물통 (C++)

2251번: 물통

bfs를 이용한 문제이다. bfs를 구현하여 물을 옮기는 경우의 수에 맞춰 물을 옮기면서 A 물통이 비었을 경우의 C 물통의 물 양을 저장해주면 된다. 문제자체는 어렵지 않게 해결할 수 있었다. 다만 경우의 수를 어떻게 반복문으로 표현할 지 떠올리는데 오래 걸린 점과 A물통이 비었을 경우라는 조건을 보지 못해 시간을 낭비했다.... 문제를 먼저 잘 이해하고 접근하자.

#include <iostream>
#include <queue>
#include <set>

using namespace std;
typedef pair<int, int> pii;

int abc[3];
bool check[201][201];
int from[6] = { 0,0,1,1,2,2 };
int to[6] = { 1,2,0,2,0,1 };
set<int> result;

void bfs() {
    queue<pii> q;

    q.push({ 0,0 });
    check[0][0] = true;
    result.insert(abc[2]);

    while (!q.empty()) {
        int now[3];
        now[0] = q.front().first;
        now[1] = q.front().second;
        now[2] = abc[2] - (now[0] + now[1]);

        q.pop();

        if (now[0] == 0) result.insert(now[2]);

        for (int i = 0; i < 6; i++) {
            int next[3] = { now[0],now[1],now[2] };
            
            if (next[to[i]] + next[from[i]] > abc[to[i]]) {
                int tmp = abc[to[i]] - next[to[i]];

                next[from[i]] = next[from[i]] - tmp;
                next[to[i]] = next[to[i]] + tmp;
            }
            else {
                next[to[i]] += next[from[i]];
                next[from[i]] = 0;
            }

            if (check[next[0]][next[1]]) continue;

            q.push({ next[0], next[1] });
            check[next[0]][next[1]] = true;
        }
    }
}

void solution() {
    bfs();

    for (auto elem : result) {
        cout << elem << " ";
    }
}

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

    cin >> abc[0] >> abc[1] >> abc[2];

    solution();

    return 0;
}