C++ / 백준 / 2251 / 물통

문제

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

2251번: 물통

문제풀이

물을 옮기는 경우는

A->B, A->C

B->A, B->C

C->A, C->B

총 6가지가 있다.

n번 물통에서 m번 물통으로 물을 옮긴다 가정하자.

n번 물통이 빌 때까지 m번 물통으로 옮기는 경우와,

m번 물통이 꽉 차 n번에서 더 이상 옮길 수 없는 경우가 있다.

이걸 식으로 나타내면

물통 M은 min(max_M, N+M), 물통 N은 N+M - min(max_M, N+M)이 된다.

visit을 set<vector<int>>로 만들어서 세 물통의 물 양이 같은 경우가 또 나오지 않도록 했다.

물통 A가 비었을때 C의 물 양을 오름차순으로 정렬해 출력해야 하므로

answer은 set형식으로 만들어주었다.

6가지 경우를 모두 해주고 이미 만든 경우의 수인지, 처음 만든 경우이면 정답으로 될 수 있는지 체크하고 다시 BFS함수를 돌린다.

 

 

코드

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
set<vector<int>>visit;
set<int>answer;
int max_A, max_B, max_C;

void BFS(int A, int B, int C) {
	int n_A = min(max_A, A + C);
	int n_B = B;
	int n_C = C + A - n_A;
	vector<int>temp = { n_A,n_B,n_C };
	if (visit.find(temp) == visit.end()) {
		visit.insert(temp);
		if (n_A == 0)
			answer.insert(n_C);
		BFS(n_A, n_B, n_C);
	}

	n_B = min(max_B, B + C);
	n_A = A;
	n_C = C + B - n_B;
	temp = { n_A,n_B,n_C };
	if (visit.find(temp) == visit.end()) {
		visit.insert(temp);
		if (n_A == 0)
			answer.insert(n_C);
		BFS(n_A, n_B, n_C);
	}

	n_A = min(max_A, A + B);
	n_B = B + A - n_A;
	n_C = C;
	temp = { n_A,n_B,n_C };
	if (visit.find(temp) == visit.end()) {
		visit.insert(temp);
		if (n_A == 0)
			answer.insert(n_C);
		BFS(n_A, n_B, n_C);
	}

	n_C = min(max_C, C + B);
	n_A = A;
	n_B = C + B - n_C;
	temp = { n_A,n_B,n_C };
	if (visit.find(temp) == visit.end()) {
		visit.insert(temp);
		if (n_A == 0)
			answer.insert(n_C);
		BFS(n_A, n_B, n_C);
	}

	n_B = min(max_B, B + A);
	n_A = A + B - n_B;
	n_C = C;
	temp = { n_A,n_B,n_C };
	if (visit.find(temp) == visit.end()) {
		visit.insert(temp);
		if (n_A == 0)
			answer.insert(n_C);
		BFS(n_A, n_B, n_C);
	}

	n_C = min(max_C, C + A);
	n_A = A + C - n_C;
	n_B = B;
	temp = { n_A,n_B,n_C };
	if (visit.find(temp) == visit.end()) {
		visit.insert(temp);
		if (n_A == 0)
			answer.insert(n_C);
		BFS(n_A, n_B, n_C);
	}
}

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

	set<int>::iterator iter;
	cin >> max_A >> max_B >> max_C;
	vector<int>temp = { max_A,max_B,max_C };
	answer.insert(max_C);
	visit.insert(temp);
	BFS(0, 0, max_C);
	for (iter = answer.begin(); iter != answer.end(); ++iter)
		cout << *iter << ' ';
}