백준 11998(Milk Pails)

www.acmicpc.net/problem/11998

11998번: Milk Pails (Silver)

 

주어진 행위를 할 때 그 행위를 할 수 있는 횟수가 주어져 있고, 그 횟수 이내에서 가장 적절한 값을 찾는것이 문제.

 

주어진 행위는 총 6가지 행위이다. 

 

a->b로 옮기기

b->a로 옮기기

a채우기

b채우기

a비우기

b비우기

 

이것만 잘 짜면 그냥 bfs로 쉽게 구현가능하다. 

 

어디서 bfs의 냄새가 났냐면 계속 반복을 하다보면 중복된게 계속해서 발생하는것을 보았고, 그러므로 시간제한에 걸리지 않을 것이라고 생각을 했다. 또 횟수가 제한되어 있는 상황에서 계속해서 반복하려면 bfs가 적절하다고 생각을 했다.

 

#include<iostream>
#include<queue>
#include<utility>
#include<cstdlib>
using namespace std;
#define MAX 105

bool check[MAX][MAX];
int X, Y, K, M;
queue<pair<pair<int, int>, int> > q;
int ans=MAX;

void bfs() {

	while (!q.empty()) {
		pair<int, int> p = q.front().first;
		int num = q.front().second;
		q.pop();

		if (num == K)return;
		int a = p.first;
		int b = p.second;
		if (a > 0) {
			if (Y - b >= a) { // a->b b가 꽉차지 않을경우 
				if (!check[0][a + b]) {
					check[0][a + b] = true;
					q.push(make_pair(make_pair(0, a + b), num + 1));
				}
			}
			else {
				if (!check[a - (Y - b)][Y]) { // b가 꽉찰 경우
					check[a - (Y - b)][Y] = true;
					q.push(make_pair(make_pair(a - (Y - b), Y), num + 1));
				}
			}
			if (!check[0][b]) { // a비우기
				check[0][b] = true;
				q.push(make_pair(make_pair(0,b), num + 1));
				if (abs(M - b) < ans)ans = abs(M - b);
			}
		}
		if (b > 0) {
			if (X - a >= b) { // b->a a가 꽉차지 않을경우
				if (!check[a+b][0]) {
					check[a + b][0] = true;
					q.push(make_pair(make_pair(a+b, 0), num + 1));
				}
			}
			else {
				if (!check[X][b-(X-a)]) { // a가 꽉찰 경우 
					check[X][b - (X - a)] = true;
					q.push(make_pair(make_pair(X, b-(X-a)), num + 1));
				}
			}
			if (!check[a][0]) { // b 비우기
				check[a][0] = true;
				q.push(make_pair(make_pair(a, 0), num + 1));
				if (abs(M - a) < ans)ans = abs(M - a);
			}
		}
		if (a < X) {
			if (!check[X][b]) { // a채우기
				check[X][b] = true;
				q.push(make_pair(make_pair(X, b), num + 1));
				if (abs(M - (X+b)) < ans)ans = abs(M - (X + b));
			}
		}
		if (b < Y) {
			if (!check[a][Y]) { // b채우기
				check[a][Y] = true;
				q.push(make_pair(make_pair(a, Y), num + 1));
				if (abs(M - (a + Y)) < ans)ans = abs(M - (a + Y));

			}
		}
		
	}
}

int main() {
	cin >> X >> Y >> K >> M;
	q.push(make_pair(make_pair(0, 0), 0));
	check[0][0] = true;
	bfs();
	cout << ans;
}