백준 2251 물통(c++)

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

2251번: 물통

이 문제는 간단하지 않은 BFS 문제입니다. 빈 물통 A, B의 용량과, 가득 찬 물통 C의 용량이 주어집니다. 이제 여기에서 각각의 물통에 물을 부어서 한 쪽이라도 물통이 비면 모든 가능한 C의 물의 양을 출력하는 경우입니다. 

 

로직

1. from -> to (모든 from의 물의 양을 부어준다.)
2. from의 물의 양 0으로 초기화
3. to에 가득찬 물의 양이 c의 양을 초과한 경우(from의 물의 양 = c의 수용량 - to의 물의 양으로 초기화)
4. 이제 물을 붓는 경우를 check 변수를 두어 방문 check (BFS적 접근)
5. from의 물의 양이 0이 된다면 가능하기에 ans변수를 true로 초기화 (C의 물 양을 출력하기 위함)

<코드>

#include <iostream>
#include <queue>

using namespace std;
bool ans[201];
bool check[201][201];
int cap[3]; // 물통의 용량
int from[] = {0, 0, 1, 1, 2 ,2}; 
int to[] = {1, 2, 0, 2, 0 , 1}; 
// 물을 부을 수 있는 방법 (x->y, x->z, y->x, y->z, z->x, z->y)
int main()
{
    for(int i=0;i<3;i++)
    {
        cin>>cap[i];
    }
    int sum = cap[2];
    queue<pair<int,int>>q;
    q.push(make_pair(0,0));
    // A,B 물통 비어있기에 0,0 push
    check[0][0] = true;
    ans[cap[2]] = true; // 안 붙는 경우도 true, 왜냐하면 한 쪽이라도 물통이 비면 조건 통과
    while(!q.empty())
    {
        int cur[3];
        cur[0] = q.front().first; // A
        cur[1] = q.front().second; // B
        cur[2] = sum - cur[0] - cur[1]; 

        q.pop();

        for(int i=0;i<6;i++) {
            int next[3] = {cur[0], cur[1], cur[2]};
            next[to[i]] += next[from[i]];
            // 물을 from -> to로 다 부어놓음
            next[from[i]] = 0; // from의 물 양 0으로 초기화

            if(next[to[i]]>= cap[to[i]]) // to의 물 양이 수용량 초과하는 경우 
            {
                next[from[i]] = next[to[i]] - cap[to[i]]; // from 물 양 = 수용량 - to의 물 양
                next[to[i]] = cap[to[i]]; // to물의 양 = cap의 양
            }

            if(!check[next[0]][next[1]]) // 0번 1번의 물의 양 만든 적 없는 경우
            {
                check[next[0]][next[1]] = true;
                q.push(make_pair(next[0], next[1]));
                if(next[0] == 0) ans[next[2]] = true; // 물통 비어 있으면, 물의 양 만들 수 있음.
            }
        } 
    }

        for(int i=0;i<=cap[2];i++)
        {
            if(ans[i]) cout<<i<<' ';
        }

}