[백준 2251] 물통

요구사항

a물통이 0이 되엇을때, c에 남을 수 잇는 물의 양 구하기

 

풀이

각 물통이 할 수 있는 행동은 두가지이다

a->b, a->c의 경로로 현재 가지고 있는 물을 이동시키는 것이다(b,c도 동일)

bfs처럼 한번 방문한 곳은 방문하지 않고 이동할 수 있는 모든 경로를 탐색한다

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
struct go {
	int x;
	int y;
	int z;
};
int visit[200][200][200];
queue<go> q;
int main() {
	int x, y, z;
	scanf("%d%d%d", &x, &y, &z);
	q.push({0,0,z });
	visit[0][0][z] = 0;
	vector<int> ans;
	while (!q.empty()) {
		int a = q.front().x;
		int b = q.front().y;
		int c = q.front().z;
		q.pop();
		//x행동 두가지
		//x->y
		//cout << a << " " << b << " " << c << endl;
		if (a == 0) {
			ans.push_back({ c });
		}

		if (a + b > y) {
			int newa = a + b - y;
			int newb = y;
			int newc = c;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}
		//전부다 x->로 이동
		else {
			int newa = 0;
			int newb = a+b;
			int newc = c;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}

		//x->z
		if (a + c > z) {
			int newa = a + c - z;
			int newb = b;
			int newc = z;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}
		else {
			int newa = 0;
			int newb = b;
			int newc = a+c;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}

		//y->x
		if (a + b > x) {
			int newa = x;
			int newb = a+b-x;
			int newc = c;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}
		//전부다 y->x로 이동
		else {
			int newa = a+b;
			int newb = 0;
			int newc = c;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}

		//y->z
		if (c + b > z) {
			int newa = a;
			int newb = c+b-z;
			int newc = z;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}
		//전부다 y->z로 이동
		else {
			int newa = a;
			int newb = 0;
			int newc = b+c;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}

		//z=>x
		if (a + c > x) {
			int newa = x;
			int newb = b;
			int newc = a+c-x;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}
		//전부다 y->x로 이동
		else {
			int newa = a+c;
			int newb = b;
			int newc = 0;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}


		//z->y
		if (c + b > y) {
			int newa = a;
			int newb = y;
			int newc = b+c -y;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}
		//전부다 y->x로 이동
		else {
			int newa = a;
			int newb = b+c;
			int newc = 0;
			if (visit[newa][newb][newc] == 0) {
				visit[newa][newb][newc] = 1;
				q.push({ newa,newb,newc });
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans[0] << " ";
	int temp = ans[0];
	for (int i = 1; i < ans.size(); i++) {
		//cout << "A" << endl;
		if (temp == ans[i]) { 
			continue; 
		}
		else {
			cout << ans[i] << " ";
			temp = ans[i];
		}
	}
}