[백준/BOJ] 2251번 물통 (C++)

www.acmicpc.net/problem/2251

2251번: 물통

BFS 유형의 문제였습니다. (다시 풀기)

세개의 물통이 있을 때, 한 물통에서 다른 하나의 물통으로 물을 쏟아붓는 경우의 수는 다음과 같습니다.

 

a->b

a->c

b->a

b->c

c->a

c->b

 

위의 6가지 경우를 BFS를 탐색해주는데, 이때 두가지 경우를 고려해줘야합니다.

 

1. 비우는 물통의 물 양 + 채우는 물통의 물 양  > 채우는 물통의 크기

2. 비우는 몰통의 물 양 + 채우는 몰틍의 물 양 <= 채우는 물통의 크기

 

물통의 크기가 각각 A, B, C, 들어있는 물의 양을 a, b, c 라 가정하고 1번 물통->2번 물통 경우의 1번이라고 하면 각각의 물통에 들어있는 물의 양은 다음과 같게 됩니다.

 

1번 물통의 물 양 : a + b - B

2번 물통의 물 양 : B

3번 물통의 물 양 : c

 

1번 물통->2번 물통 경우의 2번이라고 하면 각각의 물통에 들어있는 물의 양은 다음과 같게 됩니다.

 

1번 물통의 물 양 : 0

2번 물통의 물 양 : a + b

3번 물통의 물 양 : c

 

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

int A, B, C;
vector<int> answer;
bool visit[201][201][201];

struct Info {
    int a, b, c;
};

void BFS() {
    queue<Info> q;
    q.push( {0, 0, C} );
    
    while(!q.empty()) {
        int a = q.front().a;
        int b = q.front().b;
        int c = q.front().c;
        q.pop();
        
        if(visit[a][b][c]) continue;
        visit[a][b][c] = true;
        if(a == 0) answer.push_back(c);
        
        // a -> b
        if(a + b > B) q.push( {a + b - B, B, c} );
        else q.push( {0, a + b, c} );
        
        // a -> c
        if(a + c > C) q.push( {a + c - C, b, C} );
        else q.push( {0, b, a + c} );
        
        // b -> a
        if(b + a > A) q.push( {A, b + a - A, c} );
        else q.push( {b + a, 0, c} );
        
        // b -> c
        if(b + c > C) q.push( {a, b + c - C, C} );
        else q.push( {a, 0, b + c} );
        
        // c -> a
        if(c + a > A) q.push( {A, b, c + a - A} );
        else q.push( {c + a, b, 0} );
        
        // c -> b
        if(c + b > B) q.push( {a, B, c + b - B} );
        else q.push( {a, c + b, 0} );
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> A >> B >> C;
    BFS();
    sort(answer.begin(), answer.end());
    for(int i = 0; i < answer.size(); i++) {
        cout << answer[i] << " ";
    }
}