백준 2251 - 물통

1. 문제 정리
  - 부피가 A, B, C인 세개의 물통이 있다.

  - 초기값은 부피가 A, B인 물통은 0, C인 물통은 가득차 있다고 가정한다.

  - 물통은 한 물통이 완전히 비거나, 다른 물통이 완전히 찰 때까지 부을 수 있으며, 물의 손실은 없다.

  - 첫번째 물통(부피가 A인 물통)에 채워져 있는 물이 0일 때, 가능한 모든 마지막 물통(부피가 C인 물통)에 있을 수 있는 물의 양을 출력한다.
 
2. 접근
  - BFS로 접근하였다.

  - A->B, A->C, B->A, B->C, C->A, C->B 총 6개의 물통에서 물을 옮길 수 있는 경우의 수가 있다.

  - 6개의 경우를 이동경로로 생각하여 BFS 순회를 통해 가능한 경우의 수 중, A부피의 물통에 물이 없을 때 C 부피의 물통에 있는 물을 출력한다.
 
3. 풀이

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

struct bucket{
    int a, b, c;
}typedef bucket;

int a, b, c;
bool check[201][201][201];
vector<int> ans;

bucket move(int idx, bucket B){
    int temp;
    switch(idx){
        case 0:
            temp = B.a + B.c;
            if(temp > a) {
                B.c = temp - a;
                B.a = a;
            }
            else{
                B.a = temp;
                B.c = 0;
            }
            break;
        case 1:
            temp = B.b + B.c;
            if(temp > b) {
                B.c = temp - b;
                B.b = b;
            }
            else{
                B.b = temp;
                B.c = 0;
            }
            break;
        case 2:
            temp = B.a + B.c;
            if(temp > c) {
                B.a = temp - c;
                B.c = c;
            }
            else{
                B.c = temp;
                B.a = 0;
            }
            break;
        case 3:
            temp = B.b + B.c;
            if(temp > c) {
                B.b = temp - c;
                B.c = c;
            }
            else{
                B.c = temp;
                B.b = 0;
            }
            break;
        case 5:
            temp = B.a + B.b;
            if(temp > a) {
                B.b = temp - a;
                B.a = a;
            }
            else{
                B.b = 0;
                B.a = temp;
            }
            break;
        case 6:
            temp = B.a + B.b;
            if(temp > b) {
                B.a = temp - b;
                B.b = b;
            }
            else{
                B.a = 0;
                B.b = temp;
            }
            break;
        default: break;
    }
    return B;
}

void bfs(){
    queue<bucket> q;
    q.push({0, 0, c});
    check[0][0][c] = true;
    while(!q.empty()){
        bucket node = q.front(); q.pop();
        if(find(ans.begin(), ans.end(), node.c) == ans.end() && node.a == 0) ans.push_back(node.c);
        for(int i = 0; i < 7; i++){
            bucket next = move(i, node);
            if(check[next.a][next.b][next.c] == true) continue;
            q.push(next);
            check[next.a][next.b][next.c] = true;
        }
    }
}

int main(){
    cin >> a >> b >> c;
    bfs();
    sort(ans.begin(), ans.end());
    for(int i : ans){
        cout << i << ' ';
    }
}

  - struct bucekt : a, b, c의 각 물통에 있는 물의 부피를 저장할 구조체이다.

  - bucket move(int idx, bucket B) : idx로 정해지는 각 케이스에 따라 매개변수로 받은 B 값을 이용하여 물의 이동 후의 상태를 반환한다.

  - void bfs() : for loop의 인덱스를 7까지 하여 모든 가능한 물통의 이동 경우의 수를 검사하여 check 배열을 통해 방문하지 않았던 값에 한하여 queue에 삽입하고, 만약 현재 물통의 상태에서 A 부피의 물통이 비어있고, C 부피의 물통의 값이 ans 배열에 삽입되지 않았었다면, ans 배열에 삽입한다.
 
4. 소감

  bfs로 풀 지 고민을 좀 했던 문제였다. 단순 BruteForce로 풀 수도 있었지만, 그렇게 할 경우 이 보다도 더 코드가 지저분해질 것 같았고, 경우의 수도 더 많이 고려 해야할 것이라 생각했다. 랭크는 실버1로 되어있지만, 그보다는 좀 더 어려운 문제일 수도 있지 않을까라는 생각이 들었다.

  처음에 bfs를 공부할 때는 그 쓰임이 한정적이라 생각하였는데, 나날이 다양한 문제를 마주하면서 하나의 해결책이 아닌 다양한 해결책으로 활용할 수 있는 알고리즘이라 생각하였으며 다른 알고리즘들 또한 이처럼 하나의 수단이 아닌 다양한 해결책을 제시해준다는 점에서 더욱 알고리즘 공부가 재밌게 느껴졌다.