백준 2251번: 물통 (C++)

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

통 A가 비었을때, C에 존재할 수 있는 모든 물의 양의 경우를 출력해주면 된다.

물이 이동할 수 있는 방법은 6가지이다.

a->b, b->c ... 

초기에 각 통의 물의양은 0,0,C 이고, 6가지 모든 경우를 큐에 삽입해주고, a가 0인 순간에만 c의 물의 양을 기록해서 마지막에 출력해주면 된다.

보통 bfs문제를 풀이할 때는 큐에 삽입하는 순간에 방문처리를 해주는데, 이 문제에서는 그렇게 하면 상당히 귀찮아진다.

경우에 따라 bfs의 상단부에서 방문 검사를 해준 직후에 방문처리를 해줄수 있도록 하자.

#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
struct Info {
    int a, b, c; //a b c 물통의 현재 물의 양
};
queue<Info> q;
bool cVis[201], abVis[201][201]; 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, B, C;
    cin >> A >> B >> C; //통의 부피
 
    q.push({ 0, 0, C }); //초기 물은 C에만 가득있음
    //abVis[0][0] = true;
    //cVis[C] = true;
 
    while (!q.empty()) {
        Info cur = q.front(); //현재상태
        q.pop();
        
        //printf("%d %d %d\n", cur.a, cur.b, cur.c);
        
        if (abVis[cur.a][cur.b]) continue;
 
        abVis[cur.a][cur.b] = true;
 
        if (cur.a == 0) {
            cVis[cur.c] = true;
            //printf("%d 추가\n", cur.c);
        }
 
        // a->b
        if (cur.a + cur.b > B) {
            q.push({ cur.a - (B - cur.b), B, cur.c });
            //abVis[cur.a - (B - cur.b)][B] = true;
        }
        else {
            q.push({ 0, cur.a+cur.b, cur.c });
            //abVis[0][cur.a + cur.b] = true;
        }
        // b -> a
        if (cur.b + cur.a > A) {
            q.push({ A, cur.b-(A-cur.a), cur.c });
            //abVis[A][cur.b - (A - cur.a)] = true;
        }
        else {
            q.push({ cur.a + cur.b, 0, cur.c });
            //abVis[cur.a + cur.b][0] = true;
        }
 
        // b->c
        if (cur.b + cur.c > C) {
            q.push({ cur.a, cur.b - (C - cur.c), C });
            //abVis[cur.a][cur.b - (C - cur.c)] = true;
        }
        else {
            q.push({ cur.a, 0, cur.b + cur.c });
        //    abVis[cur.a][0] = true;
        }
 
        //c->b
        if (cur.b + cur.c > B) {
            q.push({cur.a, B, cur.c-(B-cur.b) });
            //abVis[cur.a][B] = true;
        }
        else {
            q.push({ cur.a, cur.b + cur.c, 0 });
            //abVis[cur.a][cur.b + cur.c] = true;
        }
 
        //c->a
        if (cur.c + cur.a > A) {
            q.push({A, cur.b, cur.c-(A-cur.a) });
            //abVis[A][cur.b] = true;
        }
        else {
            q.push({ cur.a + cur.c, cur.b, 0 });
        //    abVis[A][cur.b] = true;
        }
 
        //a->c
        if (cur.c + cur.a > C) {
            q.push({ cur.a-(C-cur.c), cur.b, C });
            //abVis[cur.a - (C - cur.c)][cur.b] = true;
        }
        else {
            q.push({ 0, cur.b, cur.a + cur.c });
            //abVis[0][cur.b] = true;
        }
 
    }
 
    for (int i = 0; i <= C; i++)
        if (cVis[i]) cout << i << ' ';
 
    return 0;
}