[그래프&구현] 백준 2251번 물통

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

2251번: 물통

난이도 : 실버 1

수행 시간 : 45분

 

브루트 포스적인 방법으로 풀었다. 최종 값까지 달성할때, 다른 값들을 모두 ans 벡터에 저장해놓는 방식. 

Queue를 이용한 BFS적인 접근을 통해 구현할 수 있다.

 

핵심 알고리즘은 a->b,c / b->a,c / c->a,b의 6가지 경우의 수를 모두 구현해 주면 해결된다. 

 

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

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

void input() {
	cin >> a >> b >> c;
}
void sol() {
	queue <pair<pair<int, int>, int>> q;
	q.push({ {0,0},c });
	while (!q.empty()) {
		int ax = q.front().first.first;
		int bx = q.front().first.second;
		int cx = q.front().second;
		q.pop();
		
		if (check[ax][bx] == false) {
			check[ax][bx] = true;
		}
		else
			continue;

		if (ax == 0) {
			ans.push_back(cx);
		}

		// a->b,c

		if (ax + bx > b) { //a에서 b로 물이이동할대 만약 넘친다면
			q.push({ {ax + bx - b, b }, cx });
		}
		else
			q.push({ {0,ax + bx},cx });

		if (ax + cx > c) {
			q.push({ {ax + cx - c,bx} ,c });
		}
		else
			q.push({ {0,bx},ax + cx });


		// b-> a,c
		if (ax + bx > a) {
			q.push({ {a,ax + bx - a},cx });
		}
		else
			q.push({ {ax + bx,0},cx });
		if (bx + cx > c) {
			q.push({ {ax,bx + cx - c},c });
		}
		else
			q.push({ {ax,0},bx + cx });

		//c->a,b
		if (ax + cx > a) {
			q.push({ {a,bx},ax + cx - a });
		}
		else
			q.push({ {ax + cx,bx},0 });
		if (bx + cx > b) {
			q.push({ {ax,b},bx + cx - b });
		}
		else
			q.push({ {ax,bx + cx},0 });
	}
}

int main() {
	input();
	sol();
	sort(ans.begin(), ans.end());
	for (int i = 0;i < ans.size();++i) {
		cout << ans[i] << " ";
	}
}