BOJ_2251 [ 물통 ]

문제

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

2251번: 물통

 

문제 해결 방법

모든 경우의 수를 고려해서 문제를 풀면 해결할 수 있습니다.

 

경우의 수 총 6가지가 있습니다.

1. A -> B 

2. A -> C

3. B -> A

4. B -> C

5. C -> A

6. C -> B

 

문제에서 A가 비어있을 때 C 물통에 용량을 체크해야되므로

물을 옮길 때마다 A 물통이 비어 있다면 C 용량을 체크해주기만 하면 됩니다.

 

소스 코드

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/Brute%20force/boj_2251.cpp

jokerKwu/BOJ_Algorithm

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define MAX 202
using namespace std;
bool check[MAX][MAX][MAX];
set<int> answer;
int A, B, C;
void dfs(int a, int b, int c) {
	check[a][b][c] = true;
	int tmpA = a, tmpB = b, tmpC = c;
	//A->B
	//a 있는 걸 b에 넣는거지
	if (B - b > 0) {
		if ((B - b) > a) {
			tmpA = 0; tmpB = b + a; tmpC = c;
		}
		else {
			tmpA = a - (B - b); tmpB = B; tmpC = c;
		}
		if (!check[tmpA][tmpB][tmpC]) {
			check[tmpA][tmpB][tmpC] = true;
			if (tmpA == 0) {
				answer.insert(tmpC);
			}
			dfs(tmpA, tmpB, tmpC);
		}
	}
	//A->C
	if (C - c > 0) {
		if ((C - c) > a) {
			tmpA = 0; tmpB = b; tmpC = c + a;
		}
		else {
			tmpA = a - (C - c); tmpB = b; tmpC = C;
		}
		if (!check[tmpA][tmpB][tmpC]) {
			check[tmpA][tmpB][tmpC] = true;
			if (tmpA == 0) {
				answer.insert(tmpC);
			}
			dfs(tmpA, tmpB, tmpC);
		}
	}
	//B->A
	if (A - a > 0) {
		if ((A - a) > b) {
			tmpA = a + b; tmpB = 0; tmpC = c;
		}
		else {
			tmpA = A; tmpB = b - (A - a); tmpC = c;
		}
		if (!check[tmpA][tmpB][tmpC]) {
			check[tmpA][tmpB][tmpC] = true;
			if (tmpA == 0) {
				answer.insert(tmpC);
			}
			dfs(tmpA, tmpB, tmpC);
		}
	}
	//B->C
	if (C - c > 0) {
		if ((C - c) > b) {
			tmpA = a; tmpB = 0; tmpC = c + b;
		}
		else {
			tmpA = a; tmpB = b - (C - c); tmpC = C;
		}
		if (!check[tmpA][tmpB][tmpC]) {
			check[tmpA][tmpB][tmpC] = true;
			if (tmpA == 0) {
				answer.insert(tmpC);
			}
			dfs(tmpA, tmpB, tmpC);
		}
	}
	//C->A
	if (A - a > 0) {
		if ((A - a) > c) {
			tmpA = a + c; tmpB = b; tmpC = 0;
		}
		else {
			tmpA = A; tmpB = b; tmpC = c - (A - a);
		}
		if (!check[tmpA][tmpB][tmpC]) {
			check[tmpA][tmpB][tmpC] = true;
			if (tmpA == 0) {
				answer.insert(tmpC);
			}
			dfs(tmpA, tmpB, tmpC);
		}
	}
	//C->B
	if (B - b > 0) {
		if ((B - b) > c) {
			tmpA = a; tmpB = b + c; tmpC = 0;
		}
		else {
			tmpA = a; tmpB = B; tmpC = c - (B - b);
		}
		if (!check[tmpA][tmpB][tmpC]) {
			check[tmpA][tmpB][tmpC] = true;
			if (tmpA == 0) {
				answer.insert(tmpC);
			}
			dfs(tmpA, tmpB, tmpC);
		}
	}
}

int main() {

	cin >> A >> B >> C;

	dfs(0, 0, C);
	answer.insert(C);
	for (auto it = answer.begin(); it != answer.end(); it++) cout << *it << ' ';


	return 0;
}