백준 2251번 물통

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

 

 

BFS활용 구현 문제.

너무 틀에 잡혀서 생각하지말고 여러가지 BFS나 다른 방안 생각해보기...

 

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

struct Node
{
	int A;
	int B;
	int C;
};

bool visit[201][201][201];
bool ans[201];

int main(void)
{
	int asize, bsize, csize;
	cin >> asize >> bsize >> csize;
	queue<Node> que;
	que.push({ 0,0,csize });

	vector<int> vec;

	while (!que.empty())
	{
		int a = que.front().A;
		int b = que.front().B;
		int c = que.front().C;

		que.pop();

		if (!visit[a][b][c])
		{
			visit[a][b][c] = true;
			if (!a && !ans[c])
			{
				ans[c] = true;
				vec.push_back(c);
			}

			if (a)
			{
				if (b + a <= bsize)
				{
					que.push({ 0 ,b + a ,c });
				}
				else
				{
					que.push({ b + a - bsize, bsize, c });
				}

				if (c + a <= csize)
				{
					que.push({ 0 ,b ,c + a});
				}
				else
				{
					que.push({ c + a - csize, b, csize });
				}
			}

			if (b)
			{
				if (c + b <= csize)
				{
					que.push({ a ,0 ,c + b });
				}
				else
				{
					que.push({ a , b + c - csize, csize });
				}

				if (a + b <= asize)
				{
					que.push({ a + b, 0 ,c });
				}
				else
				{
					que.push({ asize, a + b - asize ,c });
				}
			}

			if (c)
			{
				if (b + c <= bsize)
				{
					que.push({ a ,b + c, 0 });
				}
				else
				{
					que.push({ a ,bsize , b + c - bsize });
				}

				if (a + c <= asize)
				{
					que.push({ a + c, b , 0 });
				}
				else
				{
					que.push({ asize , b , a + c - asize });
				}

			}
		}
		
	}

	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << " ";
	}
	cout << endl;

}