백준 - 14867번 물통

문제

두 물통이 있는데
가득 채우기 (Fill), 다 비워버리기 (Empty), 컵 이동 (Move)
의 행동들로 물통들이 원하는 양의 물만 담고 있는 상태를 만들자!

최소 몇 번의 행동을 해야할까?

생각

최소 행동이니까 BFS로 문제 풀자 ~~

되는 행동들 다 해주고 큐에 넣어요
큐 다 꺼내도 원하는 양 크기 못 맞추면 -1 출력

queue< pair<int, pair<int, int>>> q;
pair<int, pair<int, int>> tempState;
//지금 까지 행동 수, a, b 물통에 있는 양

...
while (!q.empty()){
    tempState = q.front();

    tempa = tempState.second.first;
    tempb = tempState.second.second;

    if (tempa == c & tempb == d) {
        return tempState.first;
    }

    //fill & empty & move 해주깅//

    q.pop();
}
return -1;

fill & empty & move 처리

물통이 가득 차있는데 더 추가, 비워져있는데 또 비우기,
아무것도 없는 물통의 물을 다른 물통에 옮겨주기 같은 건 필요없을 것 같아서
if문으로 아래와 같이 처리해줌

if (tempa != a && tempb != b) {
    //fill
}

if (tempa != 0 && tempb != 0) {
    //empty
}

if (tempa != 0) {
    //move a->b
}

if (tempb != 0) {
    //move b->a
}

근데 왜 하나의 물통만 가득 차있는지 아닌지 보지 않고, 둘 다 가득 차있는지 보냐면
( if(tempa != a) (x) if(tempa != a && tempb != b) (o) )

한 쪽이 가득 차있을 때, 다른 쪽에 fill 해준다면 둘 다 가득찬 상태가 되어버리기 때문이다

둘 다 가득 찬 상태는 최소 행동으로 어떻게 (fill 2번) 만들어지는지 아니까
다양한 경로로 만들지 말고, 맨 처음에 넣어놓고, 사용했다

tempState = make_pair(0, make_pair(0, 0)); //맨 처음에 다 비워져서 시작함
q.push(tempState);
tempState = make_pair(2, make_pair(a, b)); //2번의 행동으로 둘 다 차진 물병의 상태
q.push(tempState);

+다른 분들 중엔 무조건 모든 행동의 결과가 한 쪽은 다 비었거나, 다 차있는 점을 이용해서

a가 비었을 때 b배열, b가 비었을 때 a배열,
a가 가득찼을 때 b배열, b가 가득찼을 때 a배열 을

만들어서 표기하도록 구현하는 사람도 있었다 신기해!

시간초과 1

맨 처음엔 그냥 지금까지 만든 조합 같은 건 따로 확인 안 해도
금방 돌줄 알고 했는데 시간 초과 걸려버림!!
(물통이 두 개 밖에 없어서 안 해도될거라고 생각했는데, 용량이 100000까지 가능이네 히익)

이미 탐색한 상태 저장 같은건 BFS에서 아주 중요한가봐!

vector<int> checkState[100005];
//a 물통에 물이 index만큼 들어있을 때 b에 있는 물의 양을 저장
  
if (find(checkState[newa].begin(), checkState[newa].end(), newb) == checkState[newa].end()) {
          q.push(make_pair(newlen, newState));
          checkState[newa].push_back(newb);
}

시간초과 2

그래도 시간 초과길래 구글링함

아.. 중복 없는 저장에 검색 빠르게 하는 set..
저번에도 고민하다가 사용했으면서 바보바보!!

set<int> checkState[100005];

auto p = checkState[newa].insert(newb);
if (p.second) {
          q.push(make_pair(newlen, newState));
}

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int a, b, c, d; //총 용량 두개, 원하는 용량 두개

queue< pair<int, pair<int, int>>> q;
pair<int, pair<int, int>> tempState;
//지금 까지 행동 수, a, b 물통에 있는 양

pair<int, int> newState;
set<int> checkState[100005];
//a, b 물통에 있는 양 기록

int tempa, tempb;
int resultCount;

void pushQueue(int newlen, int newa, int newb) {
	newState = make_pair(newa, newb);

	auto p = checkState[newa].insert(newb);
	if (p.second) {
		q.push(make_pair(newlen, newState));
	}
}

int findLen() {
	tempState = make_pair(0, make_pair(0, 0));
	q.push(tempState);
	tempState = make_pair(2, make_pair(a, b));
	q.push(tempState);

	while (!q.empty()) {
		tempState = q.front();

		tempa = tempState.second.first;
		tempb = tempState.second.second;

		if (tempa == c & tempb == d) {
			return tempState.first;
		}

		//fill
		if (tempa != a && tempb != b) {
			pushQueue(tempState.first + 1, a, tempb);
			pushQueue(tempState.first + 1, tempa, b);
		}

		//empty
		if (tempa != 0 && tempb != 0) {
			pushQueue(tempState.first + 1, 0, tempb);
			pushQueue(tempState.first + 1, tempa, 0);
		}

		//move a->b
		if (tempa != 0) {
			if (b - tempb < tempa) {
				pushQueue(tempState.first + 1, tempa - (b - tempb), b);
			}
			else {
				pushQueue(tempState.first + 1, 0, tempa + tempb);
			}
		}

		//move b->a
		if (tempb != 0) {
			if (a - tempa < tempb) {
				pushQueue(tempState.first + 1, a, tempb - (a - tempa));
			}
			else {
				pushQueue(tempState.first + 1, tempa + tempb, 0);
			}
		}

		q.pop();
	}
	return -1;
}

int main() {
	cin >> a >> b >> c >> d;

	cout << findLen();

	return 0;
}