[Gold / 2251] 물통

문제 링크

---

🔷 분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

✒️ 문제 설명

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

⬅️ 입력

첫째 줄에 세 정수 A, B, C가 주어진다.

➡️ 출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

💻 코드 (C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int Send[6] = {0, 0, 1, 1, 2, 2};
int Receive[6] = {1, 2, 0, 2, 0, 1};
bool visited[201][201];
vector<int> ans;
queue<pair<int, int>> q;
int now[3]; // A, B, C 값

void BFS() {
	q.push({0, 0});
	visited[0][0] = true;
	ans.push_back(now[2]);
	
	while(!q.empty()) {
		auto p = q.front();
		q.pop();
		int A = p.first;
		int B = p.second;
		int C = now[2] - A - B;
		
		// 6개 케이스 
		for(int i = 0; i < 6; i++) {
			int next[] = {A, B, C};
			next[Receive[i]] += next[Send[i]]; // 물 더하기
			next[Send[i]] = 0; // 보낸 물통은 0으로
		
			if(next[Receive[i]] > now[Receive[i]]) { // 용량 초과하면
				next[Send[i]] = next[Receive[i]] - now[Receive[i]]; // 초과 용량 돌리기
				next[Receive[i]] = now[Receive[i]]; // 꽉 채우기
			}
			if(!visited[next[0]][next[1]]) { // 방문 안했으면
				visited[next[0]][next[1]] = true; // 방문하고
				q.push({next[0], next[1]}); // 큐에 넣기
				
				if (next[0] == 0) ans.push_back(next[2]); // A 0이면 답에 넣기
			}
		}
	}
}
	
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> now[0] >> now[1] >> now[2];
	BFS();
	sort(ans.begin(), ans.end());
	for(int n : ans) cout << n << " ";
	return 0;
}