백준 2251 [C++]

www.acmicpc.net/problem/2251

2251번: 물통

1. 풀이방법

 

- 물을 옮겨 담는 횟수에 제한이 없으므로 모든 경우의 수를 다 살펴보아야겠다고 생각하여

 

- dfs를 통해서 모든 경우의 수를 탐색했습니다.

 

- 종료조건을 걸어야 할까를 고민하다가 a,b,c 에 관한 3차원배열을 선언하여,

 

- 이미 체크를 했던 물의양 set이면 재귀를 통해 들어가지 않도록 하여 종료가 되게끔 구현하였습니다.

 

- 붓는 물의 양은 붓는 쪽의 물의 양과 부으려는 물통의 빈자리 중 더 적은 양 만큼을 부었습니다

 

 

2. 주의사항

 

- 종료조건 파악 및 구현

 

 

 

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

int a, b, c;
bool already[201];
bool visitcheck[201][201][201];
vector<int> resultarr;

struct waterball {
	int ax, bx, cx;
};

void dfs(int ta, int tb, int tc) {
		visitcheck[ta][tb][tc] = true;
		if (ta==0) {
			if (already[tc] == false) {
				resultarr.push_back(tc);
				already[tc] = true;
			}
		}
		if (ta != 0 && tb != b) { //a에서 b로
			int tmpw = min((b - tb), (ta)); //b의 남은공간과 a의 물의 양중 작은 것
			if(visitcheck[ta-tmpw][tb+tmpw][tc]==false) dfs(ta - tmpw, tb + tmpw, tc);
		}
		if (ta != 0 && tc != c) { //a에서 c로
			int tmpw = min((c- tc), (ta)); //b의 남은공간과 a의 물의 양중 작은 것
			if (visitcheck[ta - tmpw][tb][tc+tmpw] == false) dfs(ta - tmpw, tb, tc+tmpw);
		}
		if (tb != 0 && tc != c) {//b에서 c로
			int tmpw = min((c - tc), (tb)); 
			if (visitcheck[ta][tb - tmpw][tc+tmpw] == false) dfs(ta , tb-tmpw, tc + tmpw);
		}
		if (tb != 0 && ta != a) {//b에서 a로
			int tmpw = min((a - ta), (tb)); 
			if (visitcheck[ta + tmpw][tb - tmpw][tc] == false)dfs(ta + tmpw, tb - tmpw, tc);
		}
		if (tc != 0 && ta != a) {//c에서 a로
			int tmpw = min((a - ta), (tc));
			if (visitcheck[ta + tmpw][tb][tc-tmpw] == false)dfs(ta + tmpw, tb , tc - tmpw);
		}
		if (tc != 0 && tb != b) {//c에서 b로
			int tmpw = min((b - tb), (tc));
			if (visitcheck[ta][tb + tmpw][tc-tmpw] == false)dfs(ta, tb + tmpw, tc - tmpw);
		}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> a >> b >> c;
	dfs(0, 0, c);
	sort(resultarr.begin(), resultarr.end());
	for (int i = 0; i < resultarr.size(); i++) {
		cout << resultarr[i] << " ";
	}
	return 0;
}