[백준] 물통 c++

문제

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

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

입력

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

출력

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

---

3개의 물통의 흐름을 배열로 선언

BFS를 이용해 구현

받는 물통에 보내려는 물통의 값을 더함 , 이 때 받는 물통이 넘친다면 넘치는 만큼 보내는 물통에 넣어주고, 받는 물통은 최대값으로 저장

#include <iostream>
#include <queue>

using namespace std;

//물을 옮기는 경우의 수를 미리 배열에 저장 (0,1) , (0,2) , (1,2) ...
static int Send[] = { 0,0,1,1,2,2 };
static int Receive[] = { 1,2,0,2,0,1 };

static bool Visited[201][201];
static bool Answer[201];
static int Now[3];

void BFS()
{
	queue<pair<int, int>> myQueue;
	myQueue.push(make_pair(0, 0));
	Visited[0][0] = true;
	Answer[Now[2]] = true;

	while (false == myQueue.empty())
	{
		pair<int, int> p = myQueue.front();
		myQueue.pop();

		int a = p.first;
		int b = p.second;

		//3번 용기 = 전체물의 양에서 a,b를 뺀것
		int c = Now[2] - a - b;

		for (int i = 0; i < 6; i++)
		{
			int next[] = { a,b,c };
			next[Receive[i]] += next[Send[i]];
			next[Send[i]] = 0;

			//넘치는 양에 대한 처리
			if (next[Receive[i]] > Now[Receive[i]])
			{
				next[Send[i]] = next[Receive[i]] - Now[Receive[i]];
				next[Receive[i]] = Now[Receive[i]];
			}

			//방문한 적이 없는 곳에 대한 처리
			if (false == Visited[next[0]][next[1]])
			{
				Visited[next[0]][next[1]] = true;
				myQueue.push(make_pair(next[0], next[1]));

				if (next[0] == 0)
				{
					Answer[next[2]] = true;
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> Now[0] >> Now[1] >> Now[2];

	BFS();

	for (int i = 0; i < 201; i++)
	{
		if (Answer[i])
		{
			cout << i << " ";
		}
	}
}

 

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