백준 2251 - 물통 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/2251

풀이전략

1. 이 문제에 경우 물이 이동하는 모든 경우를 고려해야한다. 즉 A->B, A->C, B->C, B->A, C->A, C->B 이 모든 경우들을 하나하나 고려해서 큐에 넣어주어야한다.
2. 모든 문제들이 다 일반적인 BFS로 풀릴거라는 착각에서 벗어나야한다. 모든 경우들을 하나하나줄때 예를들어 A->B로 물을 넣어줄 때, A+B에 B가 꽉찰경우, 그렇지 않을경우로 나눠서 케이스 분류를 해주어야한다.
3. A, B, C의 물들이 어느정도 채워져있는지를 찾는 스트럭쳐가 필요하고, 중복을 피하기위한 ch배열이 필요하다.

코드

#include<bits/stdc++.h>

using namespace std;

struct Data{
    int a, b, c;
    Data(int x, int y, int z){
        a =x;
        b = y;
        c = z;
    }
};

int A, B, C;
bool chk[202][202], ans[202];

void bfs(){
    queue<Data> q;
    // 초기 상태에는 C 물통에 꽉 차 있으므로 이 상황에서 BFS를 시작한다.
    q.push(Data(0,0,C));

    while(!q.empty()){
        Data now = q.front();
        q.pop();
		
        // 이미 한 경우일때는 그냥 패스
        if(chk[now.a][now.b]) continue;
		// 중요한 포인트! 어차피 a b의 물의 양이 정해졌다면 c의 물의양이 어느정도 일지는 자명하다. 따라서 2차원 배열로 모든 경우를 다 저장할 수 있다. 
        chk[now.a][now.b] = true;
		// a가 0일 경우가 우리가 찾는 경우이기 때문
        if(now.a == 0) ans[now.c] = true;


		//// 이 밑에서부터 중요한 경우이다.
        // 두 물을 합쳤을때 넘칠경우, 그렇지 않을 경우를 계산해준 부분이다. 
        //a -> b
        if(now.a + now.b > B) q.push(Data(now.a+now.b-B, B, now.c));
        else q.push(Data(0, now.a+now.b, now.c));
        //a->c
        if(now.a + now.c > C) q.push(Data(now.a+now.b - C, now.b, C));
        else q.push(Data(0, now.b, now.a+now.c));
        //b->a
        if(now.b + now.a > A) q.push(Data(A, now.b+now.a - A, now.c));
        else q.push(Data(now.b+now.a, 0, now.c));
        //b->c
        if(now.b + now.c  > C) q.push(Data(now.a, (now.b+now.c)-C, C));
        else q.push(Data(now.a, 0, now.b+now.c));
        //c->a
        if(now.c + now.a > A) q.push(Data(A, now.b, now.c+now.a - A));
        else q.push(Data(now.c + now.a, now.b, 0));
        //c->b
        if(now.c + now.b > B) q.push(Data(now.a, B, now.c + now.b - B));
        else q.push(Data(now.a, now.c+now.b, 0));
    }
}
void print(){
    for(int i=0; i<=C; i++){
        if(ans[i]) printf("%d ",i);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    cin >> A >> B >> C;
    bfs();
    print();
    return 0;
}

소감

나는 이 문제를 해결하지 못하였다. 지금까지 bfs들은 다 깔끔하게 떨어질거라고만 생각했기 때문이다. 이 문제처럼 모든 경우를 다 생각해줘야 할 때도 항상 고려해줘야 한다. 또한 A, B, C가 서로 연관되어 있으므로 A, B두개만 저장하는 2차원 배열로 충분히 C의 값까지 유추 가능하기 때문에 효율성을 위해 3차원 배열이 아닌 2차원배열을 택한것에 유의해야한다.