백준 2251: 물통

문제 요약

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

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

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS
• BFS

문제 풀이

각 물통 A,B,C를 하나의 배열로 취급하여 탐색하면 된다. 나는 BFS탐색으로 풀었지만, DFS로도 풀 수 있을 것 같다.

큐에 삽입할 자료형은 vector<int>로, 0번, 1번, 2번 인덱스가 각각 A,B,C의 물통을 가리킨다. 중복 여부는 set으로 파악하였고, A물통이 비었을 때, 즉 0번 인덱스의 값이 0일 때에만 cnt배열을 true로 만들어 주어서, 마지막에 true인 값만 골라 쭉 파악해 주었다.

물통을 붓는 과정에서는, i번 물통에서 j번 물통으로 물을 붓는 것으로 생각하여, i와 j가 같지 않을 경우에만 연산하였다. i번 물통에 물이 없을 때, 혹은 j번 물통이 가득 찼을 때에도 물을 붓는 것은 불가능하다. 따라서 i번 물통에 물이 있고, j번 물통도 가득 차지 않을 때만 물을 부어주었는데, 물을 붓는 양은 (i번째 물통에 있는 물의 양)과 (j번째 물통의 최대 용량 - j번째 물통의 현재 용량)의 최소값과 같다. 이 수를 기반으로 물을 부은 뒤, 물을 부었을 때 중복 여부를 확인한 후, 처음으로 보인 물통 별 양의 패턴이라면 set에 추가, 큐에 푸쉬, 또한 0번째 물통(A)이 비어있다면, 2번째 물통(C)의 양도 cnt로 표시해주었다.

마지막에 0부터 200까지 돌면서 cnt의 값이 true인 경우에만 i를 출력해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>

bool cnt[201];

using namespace std;

int main() {
	queue<vector<int>> q;
	set<vector<int>> s;
	vector<int> v;
	int in, qsize, level = -1;
	for (int i = 0; i < 3; i++) {
		cin >> in;
		v.push_back(in);
	}
	s.insert({ 0,0,v[2] });
	q.push({ 0,0,v[2] });
	cnt[v[2]] = true;
	while (!q.empty()) {
		qsize = q.size();
		level++;
		while (qsize--) {
			auto val(q.front());
			q.pop();
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					auto cop(val);
					if (i == j) continue;
					if (cop[i] > 0 && cop[j] < v[j]) {
						int temp = min(cop[i], v[j] - cop[j]);
						cop[i] -= temp;
						cop[j] += temp;
						if (s.count(cop) == 0) {
							s.insert(cop);
							if(cop[0] == 0) cnt[cop[2]] = true;
							q.push(cop);
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= 200; i++) {
		if (cnt[i]) printf("%d ", i);
	}
	return 0;
}