물통

물통  A,B,C의 물의 양을 각각의 NODE라고 생각했고, 그리고 물을 옮기는 행위에 대한것을 따르거나, 따르지않거나 즉 따를때 1, 따르지 않을때 0의 가중치를 가지고있어서, BFS로 충분히 풀수있으리라고 생각했다.

 

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int x[201][201][201];
bool d[201][201][201];
int a, b, c;
struct go{
	int a, b, c;
	go(int a, int b, int c) {
		this->a = a;
		this->b = b;
		this->c = c;
	}
};
vector<int> zp;


void bfs() {
	queue<go> q;
	q.push(go(0, 0, c));
	d[0][0][c] = true;
	while (!q.empty()) {
		go x = q.front();
		int xx = x.a; int yy = x.b; int zz = x.c;
		if (xx == 0) {
			zp.push_back(zz);
		}
		q.pop();
		//a에 b
		if (xx + yy > a) {
			int ny = (xx + yy) - a;
			int nx = a;
			if (d[nx][ny][zz] == false) {
				d[nx][ny][zz] = true;
				q.push(go(nx, ny, zz));
			}
		}
		if (xx + yy <= a) {
			int ny = 0;
			int nx = xx + yy;
			if (d[nx][ny][zz] == false) {
				d[nx][ny][zz] = true;
				q.push(go(nx, ny, zz));
			}
		}
		//a 에 c
		if (xx + zz > a) {
			int nz = (xx + zz) - a;
			int nx = a;
			if (d[nx][yy][nz] == false) {
				d[nx][yy][nz] = true;
				q.push(go(nx, yy, nz));
			}
		}
		if (xx + zz <= a) {
			int nz = 0;
			int nx = xx + zz;
			if (d[nx][yy][nz] == false) {
				d[nx][yy][nz] = true;
				q.push(go(nx, yy, nz));
			}
		}
		//b에 c
		if (yy + zz > b) {
			int nz = (yy + zz) - b;
			int ny = b;
			if (d[xx][ny][nz] == false) {
				d[xx][ny][nz] = true;
				q.push(go(xx, ny, nz));
			}
		}
		if (yy + zz <= b) {
			int nz = 0;
			int ny = yy + zz;
			if (d[xx][ny][nz] == false) {
				d[xx][ny][nz] = true;
				q.push(go(xx, ny, nz));
			}
		}
		//b 에 a
		if (yy + xx > b) {
			int nx = (yy + xx) - b;
			int ny = b;
			if (d[nx][ny][zz] == false) {
				d[nx][ny][zz] = true;
				q.push(go(nx, ny, zz));
			}
		}
		if (yy + xx <= b) {
			int nx = 0;
			int ny = yy + xx;
			if (d[nx][ny][zz] == false) {
				d[nx][ny][zz] = true;
				q.push(go(nx, ny, zz));
			}
		}
		//c 에 a
		if (zz + xx > c) {
			int nx = (zz + xx) - c;
			int nz = c;
			if (d[nx][yy][nz] == false) {
				d[nx][yy][nz] = true;
				q.push(go(nx, yy, nz));
			}
		}
		if (zz + xx <= c) {
			int nx = 0;
			int nz = zz + xx;
			if (d[nx][yy][nz] == false) {
				d[nx][yy][nz] = true;
				q.push(go(nx, yy, nz));
			}
		}
		//c 에 b
		if (zz + yy > c) {
			int ny = (zz + yy) - c;
			int nz = c;
			if (d[xx][ny][nz] == false) {
				d[xx][ny][nz] = true;
				q.push(go(xx, ny, nz));
			}
		}
		if (zz + yy <= c) {
			int ny = 0;
			int nz = zz + yy;
			if (d[xx][ny][nz] == false) {
				d[xx][ny][nz] = true;
				q.push(go(xx, ny, nz));
			}
		}
	}

}

int main() {
	
	scanf("%d %d %d", &a, &b, &c);
	//d[0][0][c] = true;
	bfs();
	sort(zp.begin(), zp.end());
	for (int i = 0; i<zp.size(); i++) {
		printf("%d ", zp[i]);
	}
	printf("\n");
	return 0;
}

위와같이 풀었고 처음에는, 문제 예제에 주어지는 A,B,C가 계속 초기물량인줄알았는데, C만 가득차있고 A,B가 0임을 숙지하면 충분히 쉽게 풀수있는 문제다. 배열이 3차원인데, C의 물의 양은 초기 C- (A+B의 현재물양) 으로 구할수있어서

2차원배열로 해도좋을거같다. 근데 사실 확신이 안들어서 3차원으로 진행했고,

int 는 필요할것같아서 썼는데, 코드작성하다보니 딱히 쓸모가없어서 사용하지않았다.