BOJ_2251 : 물통

문제

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

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

입력

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

출력

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

C++ 코드

#include <iostream>
#include <queue>

using namespace std;

bool check[205][205];
bool ans[205];
int max_size[3];


int main() {
	// 물통의 사이즈
	for (int i = 0; i < 3; i++)
		cin >> max_size[i];

	queue<pair<int, int> > q;

	q.push(make_pair(0, 0));
	check[0][0] = true;
	ans[max_size[2]] = true;

	while (!q.empty()) {
		int abc[3];
		abc[0] = q.front().first;
		abc[1] = q.front().second;
		abc[2] = max_size[2] - abc[0] - abc[1];
		q.pop();

		for (int i = 0; i < 3; i++) {
			if (abc[i] == 0) continue;
			// 현재 물통이 비었다면 패스

			int new_abc[3];
			int next = (i + 1) % 3; // 다음 물통
			int next2 = (i + 2) % 3; // 다음음 물통

			// 다음 물통에 자리가 있다면
			if (abc[next] < max_size[next]) {
				new_abc[i] = 0;
				new_abc[next] = abc[next] + abc[i];
				new_abc[next2] = abc[next2];

				// 물이 넘친다면
				if (new_abc[next] > max_size[next]) {
					new_abc[i] = new_abc[next] - max_size[next];
					new_abc[next] = max_size[next];
				}
				// 탐색을 안했다면
				if (check[new_abc[0]][new_abc[1]] == false) {
					check[new_abc[0]][new_abc[1]] = true;
					q.push(make_pair(new_abc[0], new_abc[1]));
					if(new_abc[0] == 0)
						ans[new_abc[2]] = true;
				}
			}
				// 다음 다음 물통에 자리가 있다면
			if (abc[next2] < max_size[next2]) {
					new_abc[i] = 0;
					new_abc[next2] = abc[next2] + abc[i];
					new_abc[next] = abc[next];

					// 물이 넘친다면
					if (new_abc[next2] > max_size[next2]) {
						new_abc[i] = new_abc[next2] - max_size[next2];
						new_abc[next2] = max_size[next2];
					}
					// 탐색을 안했다면
					if (check[new_abc[0]][new_abc[1]] == false) {
						check[new_abc[0]][new_abc[1]] = true;
						q.push(make_pair(new_abc[0], new_abc[1]));
						if(new_abc[0] == 0 )
							ans[new_abc[2]] = true;
					}
			}
		}
	}

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

	cout << '\n';

	return 0;

}