[백준 14867] 물통

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

14867번: 물통

#include <cstdio>
#include <queue>
#include <set>
int a, b, c, d;

using namespace std;

struct _st
{
	int x;
	int y;
	int cnt;
};

queue<_st> Q;		// 상태 저장용 큐
	
set<pair<int, int>> S;	// set으로 방문 체크를 대신한다


void Fill_A(int x, int y, int cnt)
{
	// Fill A
	if (S.find({ a, y }) != S.end()) return;
	Q.push({ a, y , cnt + 1});
	S.insert({ a, y });
}

void Fill_B(int x, int y, int cnt)
{
	// Fill B
	if (S.find({ x, b }) != S.end()) return;
	Q.push({ x, b , cnt + 1});
	S.insert({ x, b });
}


void Empty_A(int x, int y, int cnt)
{
	// Empty A
	if (S.find({ 0, y }) != S.end()) return;
	Q.push({ 0, y, cnt + 1 });
	S.insert({ 0, y });
}

void Empty_B(int x, int y, int cnt)
{
	// Empty B
	if (S.find({ x, 0 }) != S.end()) return;
	Q.push({ x, 0, cnt + 1 });
	S.insert({ x, 0 });
}


void Move_AtoB(int x, int y, int cnt)
{
	// A -> B
	if (x <= b - y && S.find({ 0, y + x }) == S.end()) {
		Q.push({ 0, y + x, cnt + 1});
		S.insert({ 0, y + x });
	}
	else if (x > b - y && S.find({ x - (b - y), b }) == S.end()) {
		Q.push({ x - (b - y), b, cnt + 1});
		S.insert({ x - (b - y), b });
	}
}



void Move_BtoA(int x, int y, int cnt)
{
	// B -> A
	if (y <= a - x && S.find({ x + y, 0 }) == S.end()) {
		Q.push({ x + y, 0, cnt + 1});
		S.insert({ x + y , 0 });
	}
	else if (y > a - x && S.find({ a, y - (a - x) }) == S.end()) {
		Q.push({ a, y - (a - x), cnt + 1});
		S.insert({ a, y - (a - x) });
	}
}



int BFS(void)
{	
	Q.push({ 0, 0, 0 });	// 큐에 초기 상태 삽입
	S.insert({ 0, 0 });	// 집합에 초기 상태 삽입 

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.x == c && data.y == d) return data.cnt;

		Fill_A(data.x, data.y, data.cnt);
		Fill_B(data.x, data.y, data.cnt);
		Empty_A(data.x, data.y, data.cnt);
		Empty_B(data.x, data.y, data.cnt);
		Move_AtoB(data.x, data.y, data.cnt);
		Move_BtoA(data.x, data.y, data.cnt);
	
	}
	return -1;
}



int main()
{
	scanf("%d %d %d %d", &a, &b, &c, &d);	// (a, b) 용량 (c, d) 목적 상태
	int ans = BFS();
	printf("%d", ans);
	return 0;
}

사실 로직은 빨리 나왔는데 2차원 방문배열을 만들어서 A 물통에 남아있는 물의 양/ B 물통에 남아있는 물의 양을 기준으로 작업횟수를 기록하려고 하니, 메모리 제한 때문에 chk[100000 + 2][100000 + 2] 배열이 생성되지 않았다.

그래서 원소의 중복 저장이 불가한 set을 사용하여, 해당 pair가 집합의 원소라면 무시하고 집합의 원소가 아니라면 삽입하여 상태 발전(작업 진행, 작업 횟수 증가)을 하도록 코드를 구현했다. 

 

 

// 컨테이너 선언

구조체 _st 는 A 물통에 남아있는 물의 양, B 물통에 남아있는 물의 양, 작업 횟수를 기록하기 위함이다. 이러한 타입의 queue를 만들어 상태발전을 위해 사용하였다. 

set S는 int의 pair 타입으로 생성해 주었다. 사실 set도 구조체로 만들고 싶었지만,,, 뭐 커스텀 함수 만들고 그래야 한대서,,, 작업횟수는 그냥 큐에 하기로.

 

 

// BFS()

사실 이 문제는 컨테이너 선언이 전부이다. 다른건 일반 BFS 풀이처럼 진행하면 된다. 

한 가지 다른 점은 기존에는 chk 배열을 확인하면서 현재 진행된 상태의 작업횟수가 기존 배열에 저장된 수 보다 작아야만 갱신을 해줬다. 그런데 여기서는 방문 표시를 위해 set을 사용한 만큼 A와 B에 남아있는 양(pair)이 set의 원소로 존재한다면, 현재 그 상태가 만들어지기까지의 작업상태보다 훨씬 더 이전에 해당 상태가 되어 set에 담겼다고 이해할 수 있다. 따라서 이 경우 각 상태발전 함수를 바로 리턴해준다. 

한편 현재의 상태가 set의 원소로 존재하지 않으면 이전에 그 상태가 한번도 만들어지지 않았다는 것이므로, 현재 작업횟수가 최선의 횟수가 된다. 따라서 이를 Q와 S에 각각 삽입해준다.