[C++] 백준 2251번: 물통

문제 링크

2251번: 물통

문제 요약

물통의 용량 A, B, C가 주어지고, 초기에는 C만 가득 차 있는 상태이다. 물통의 물을 한 물통이 비거나 다른 물통이 꽉 찰때까지 횟수 제한 없이 옮길 수 있다.
A 물통이 비었을 때 C 물통에 담겨 있을 수 있는 물의 양을 모두 출력한다.

접근 방법

너비 우선 탐색을 통해서 해결할 수 있습니다. 큐에 양동이 세 개의 물의 양을 모두 집어 넣어주면서 너비 우선 탐색을 돌리면 됩니다. 그 과정에서 양동이에서 물을 옮기는 과정에서 각 양동이의 용량에 대한 제한만 잘 관리해주면 됩니다.

방문 여부의 확인은 어차피 A, B, C 모두 200 이하이기 때문에 3차원 불리언 배열로 관리해도 됩니다.

가능한 C의 값을 저장하는 자료구조로는 중복 요소의 배제와 정렬이 자동으로 되기 때문에 std::set을 사용했습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 201

using namespace std;

int sz[3];

struct Info {
	int bucket[3];

	void pour(int from, int to)
	{
		if (!bucket[from])
			return;

		if (sz[to] - bucket[to] < bucket[from])
		{
			bucket[from] -= (sz[to] - bucket[to]);
			bucket[to] = sz[to];
		}
		else
		{
			bucket[to] += bucket[from];
			bucket[from] = 0;
		}
	}
};

bool visited[MAX][MAX][MAX];
set<int> res;

int main(void)
{
	FASTIO;
	cin >> sz[0] >> sz[1] >> sz[2];

	queue<Info> q;
	q.push({ 0, 0, sz[2] });
	visited[0][0][sz[2]] = true;

	while (!q.empty())
	{
		Info now = q.front();
		q.pop();
		if (!now.bucket[0])
			res.insert(now.bucket[2]);

		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				if (i == j)
					continue;
				Info next = now;
				next.pour(i, j);

				if (!visited[next.bucket[0]][next.bucket[1]][next.bucket[2]])
				{
					visited[next.bucket[0]][next.bucket[1]][next.bucket[2]] = true;
					q.push(next);
				}

			}
		}
	}

	for (set<int>::iterator it = res.begin(); it != res.end(); it++)
		cout << *it << ' ';
	return 0;
}