2251번: 물통

문제링크: 2251번: 물통

문제

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

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

입력

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

출력

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

설명

A,B,C에 대한 그래프탐색 문제으로 물통 값이 200으로 201*201*210로 비교적 작은 배열크기를 가진다. 물통의 물을 옮기는 과정에서 6개의 분기로 나뉘는데 각 분기별로 탐색을 진행하면된다.

1. A->B
2. A->C
3. B->A
4. B->C
5. C->A
6. C->B

물론, 탐색문제이기 때문에 탐색을 진행할 때 이미 진행한 구간인지 확인해주어야 한다.

탐색을 완료한 뒤에는 A가 0이고 모든 B,C에 대해서 true일 때 C값을 저장하고 중복없이 값을 출력하면된다.

쉬운 중복제거를 위해 set을 사용하였고 출력할 때는 오름차순으로 출력하였다.

코드

#include <iostream>
#include <queue>
#include <set>
#define endl '\n'
#define MAX 201

using namespace std;

struct State {
	int A, B, C;
	State(int ia, int ib, int ic) {
		A = ia, B = ib, C = ic;
	}
};

bool check[MAX][MAX][MAX] = { false };

void solve() {
	int startA, startB, startC;
	cin >> startA >> startB >> startC;

	queue<State> q;
	q.push(State(0, 0, startC));
	check[0][0][startC] = true;
	while (!q.empty()) {
		int nowA = q.front().A, nowB = q.front().B, nowC = q.front().C;
		q.pop();

		int nextA, nextB, nextC, move;

		// A -> B
		move = min(nowA, startB - nowB);
		nextA = nowA - move, nextB = nowB + move, nextC = nowC;
		if (check[nextA][nextB][nextC] == false) {
			q.push(State(nextA, nextB, nextC));
			check[nextA][nextB][nextC] = true;
		}

		// A -> C
		move = min(nowA, startC - nowC);
		nextA = nowA - move, nextB = nowB, nextC = nowC + move;
		if (check[nextA][nextB][nextC] == false) {
			q.push(State(nextA, nextB, nextC));
			check[nextA][nextB][nextC] = true;
		}

		// B -> A
		move = min(nowB, startA - nowA);
		nextA = nowA + move, nextB = nowB - move, nextC = nowC;
		if (check[nextA][nextB][nextC] == false) {
			q.push(State(nextA, nextB, nextC));
			check[nextA][nextB][nextC] = true;
		}

		// B -> C
		move = min(nowB, startC - nowC);
		nextA = nowA, nextB = nowB - move, nextC = nowC + move;
		if (check[nextA][nextB][nextC] == false) {
			q.push(State(nextA, nextB, nextC));
			check[nextA][nextB][nextC] = true;
		}

		// C -> A
		move = min(nowC, startA - nowA);
		nextA = nowA + move, nextB = nowB, nextC = nowC - move;
		if (check[nextA][nextB][nextC] == false) {
			q.push(State(nextA, nextB, nextC));
			check[nextA][nextB][nextC] = true;
		}

		// C -> B
		move = min(nowC, startB - nowB);
		nextA = nowA, nextB = nowB + move, nextC = nowC - move;
		if (check[nextA][nextB][nextC] == false) {
			q.push(State(nextA, nextB, nextC));
			check[nextA][nextB][nextC] = true;
		}
	}

	set<int> setC;
	for (int i = 0; i < MAX; ++i) {
		for (int j = 0; j < MAX; ++j) {
			if (check[0][i][j]) {
				setC.insert(j);
			}
		}
	}

	for (auto c : setC) {
		cout << c << ' ';
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
	solve();
	return 0;
}