[BOJ/Gold 5] 백준 2251 물통(C++)

문제 링크

https://www.acmicpc.net/problem/2251

2251번: 물통

문제

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

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

입력

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

출력

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

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10

 

알고리즘 분류

• 그래프 탐색

풀이

visited[CurA][CurB][CurC], 즉 물통의 양이 A가 CurA, B가 CurB, C가 CurC인 상태는 방문했고 다시 탐색하지 않는다는 boolean 변수 배열을 선언한다.

그리고 BFS를 사용하여 다음과 같은

1. A에서 B로 물을 따를 때

2. A에서 C로 물을 따를 때

3. B에서 A로 물을 따를 때

4. B에서 C로 물을 따를 때

5. C에서 A로 물을 따를 때

6. C에서 B로 물을 따를 때

6가지의 경우에 따른 변화한 물의 양을 탐색한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 205
#define LL long long
#define INF 2e9

using namespace std;
int Water[MAX];
bool visited[MAX][MAX][MAX];
vector<int> answer;

void BFS(int A, int B, int C) {
	queue<pair<pair<int, int>, int> > Q;
	Q.push(make_pair(make_pair(A, B), C));

	while (!Q.empty()) {
		int CurA = Q.front().first.first;
		int CurB = Q.front().first.second;
		int CurC = Q.front().second;
		Q.pop();

		if (visited[CurA][CurB][CurC]) {
			continue;
		}
		visited[CurA][CurB][CurC] = true;

		if (CurA == 0) {
			answer.push_back(CurC);
		}

		int nextA, nextB, nextC;
		// A에서 B로 물을 따를 때
		if (CurA > Water[1] - CurB) {
			nextA = CurA + CurB - Water[1];
			nextB = Water[1];
			nextC = CurC;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		else {
			nextA = 0;
			nextB = CurA + CurB;
			nextC = CurC;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		// A에서 C로 물을 따를 때
		if (CurA > Water[2] - CurC) {
			nextA = CurA + CurC - Water[2];
			nextB = CurB;
			nextC = Water[2];
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		else {
			nextA = 0;
			nextB = CurB;
			nextC = CurA + CurC;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		// B에서 A로 물을 따를 때
		if (CurB > Water[0] - CurA) {
			nextA = Water[0];
			nextB = CurA + CurB - Water[0];
			nextC = CurC;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		else {
			nextA = CurA + CurB;
			nextB = 0;
			nextC = CurC;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		// B에서 C로 물을 따를 때
		if (CurB > Water[2] - CurC) {
			nextA = CurA;
			nextB = CurB + CurC - Water[2];
			nextC = Water[2];
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		else {
			nextA = CurA;
			nextB = 0;
			nextC = CurB + CurC;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		// C에서 A로 물을 따를 때
		if (CurC > Water[0] - CurA) {
			nextA = Water[0];
			nextB = CurB;
			nextC = CurA + CurC - Water[0];
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		else {
			nextA = CurA + CurC;
			nextB = CurB;
			nextC = 0;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		// C에서 B로 물을 따를 때
		if (CurC > Water[1] - CurB) {
			nextA = CurA;
			nextB = Water[1];
			nextC = CurB + CurC - Water[1];
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
		else {
			nextA = CurA;
			nextB = CurB + CurC;
			nextC = 0;
			Q.push(make_pair(make_pair(nextA, nextB), nextC));
		}
	};
}

int main() {
	FIRST
	for (int i = 0; i < 3; i++) {
		cin >> Water[i];
	}
	BFS(0, 0, Water[2]);
	sort(answer.begin(), answer.end());
	answer.erase(unique(answer.begin(), answer.end()), answer.end());
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << " ";
	}
	cout << "\n";

	return 0;
}