[BOJ] 2251 물통

문제 요약

문제 링크: 백준 2251 - 물통

문제 설명

---

접근 방법

하나의 물통에서 다른 물통으로 옮기는 경우의 수 6가지를 모두 탐색해주면 된다. 그리고 A가 0일때의 C 값을 저장하여 출력하면 된다. BFS로 구현하였다.

풀이 코드는 2개를 첨부하였는데, 첫 번째 풀이 이후, 너무 코드가 길고 가독성이 떨어지는 것 같아서 반복문으로 효율적으로 구현한 두 번째 풀이도 작성하였다. 두 풀이 코드의 로직은 동일하다.

---

코드

// 첫 번째 풀이: 각 물통에서 다른 물통으로 이동하는 경우를 직접 일일이 조건문으로 코드작성

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

int a, b, c;
bool vis[201][201][201];
vector<int>ans;

void solve() {
	queue<tuple<int, int, int>>q;
	vis[0][0][c] = 1;
	q.push({ 0,0,c });
	while (q.size()) {
		int aa = get<0>(q.front());
		int bb = get<1>(q.front());
		int cc = get<2>(q.front());
		q.pop();
		if (aa == 0)
			ans.push_back(cc);
		if (cc > a - aa) {
			if (!vis[a][bb][cc - (a - aa)]) {
				vis[a][bb][cc - (a - aa)] = 1;
				q.push({ a, bb, cc - (a - aa) });
			}
		}
		else {
			if (!vis[aa + cc][bb][0]) {
				vis[aa + cc][bb][0] = 1;
				q.push({ aa + cc, bb, 0 });
			}
		}
		if (cc > b - bb) { 
			if (!vis[aa][b][cc - (b - bb)]) {
				vis[aa][b][cc - (b - bb)] = 1;
				q.push({ aa, b, cc - (b - bb) });
			}
		}
		else { 
			if (!vis[aa][bb + cc][0]) {
				vis[aa][bb + cc][0] = 1;
				q.push({ aa, bb + cc, 0 });
			}
		}
		if (bb > a - aa) { 
			if (!vis[a][bb - (a - aa)][cc]) {
				vis[a][bb - (a - aa)][cc] = 1;
				q.push({ a, bb - (a - aa), cc });
			}
		}
		else {
			if (!vis[aa + bb][0][cc]) {
				vis[aa + bb][0][cc] = 1;
				q.push({ aa + bb, 0, cc });
			}
		}
		if (bb > c - cc) { 
			if (!vis[aa][bb - (c - cc)][c]) {
				vis[aa][bb - (c - cc)][c] = 1;
				q.push({ aa, bb - (c - cc), c });
			}
		}
		else { 
			if (!vis[aa][0][cc + bb]) {
				vis[aa][0][cc + bb] = 1;
				q.push({ aa, 0, cc + bb });
			}
		}
		if (aa > b - bb) {
			if (!vis[aa - (b - bb)][b][cc]) {
				vis[aa - (b - bb)][b][cc] = 1;
				q.push({ aa - (b - bb), b, cc });
			}
		}
		else {
			if (!vis[0][bb + aa][cc]) {
				vis[0][bb + aa][cc] = 1;
				q.push({ 0, bb + aa, cc });
			}
		}
		if (aa > c - cc) { 
			if (!vis[aa - (c - cc)][bb][c]) {
				vis[aa - (c - cc)][bb][c] = 1;
				q.push({ aa - (c - cc), bb, c });
			}
		}
		else { 
			if (!vis[0][bb][cc + aa]) {
				vis[0][bb][cc + aa] = 1;
				q.push({ 0, bb, cc + aa });
			}
		}
	}
	sort(ans.begin(), ans.end());
	for (auto i : ans) cout << i << ' ';
}

void input() {
	cin >> a >> b >> c;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	input();
	solve();
}

 

// 두 번째 풀이: 물병 간의 이동 경우의 수를 반복문으로 구현

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

int v[3];
bool vis[201][201][201];
vector<int>ans;

void solve() {
	queue<tuple<int, int, int>>q;
	q.push({ 0,0,v[2] });
	int from[] = { 0, 0, 1, 1, 2, 2 };
	int to[] = { 1, 2, 0, 2, 0, 1 };
	while (q.size()) {
		int a = get<0>(q.front());
		int b = get<1>(q.front());
		int c = get<2>(q.front());
		int abc[3] = { a,b,c };
		q.pop();
		if (vis[a][b][c])
			continue;
		else
			vis[a][b][c] = 1;
		if (a == 0)
			ans.push_back(c);
		for (int i = 0; i < 6; i++) {
			int f = from[i];
			int t = to[i];
			int next_abc[3] = { a,b,c };
			if (abc[f] > v[t] - abc[t]) {
				int move = v[t] - abc[t];
				next_abc[f] -= move;
				next_abc[t] += move;
				q.push({ next_abc[0],next_abc[1] ,next_abc[2] });
			}
			else {
				int move = abc[f];
				next_abc[f] -= move;
				next_abc[t] += move;
				q.push({ next_abc[0],next_abc[1] ,next_abc[2] });
			}
		}
	}
	sort(ans.begin(), ans.end());
	for (auto i : ans) cout << i << ' ';
}

void input() {
	for (int i = 0; i < 3; i++) cin >> v[i];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	input();
	solve();
}