[BOJ / 메모이제이션 BFS] 14867 물통

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

14867번: 물통

 

14867 물통

알고리즘 : 메모이제이션을 활용한 BFS

얼핏보면 간단 dp같지만, 두 물통의 총량이 100,000으로 두 값을 dp배열의 크기로 사용하면 메모리초과가 납니다.

하지만 나오는 물의 경우의 수는 한정적이므로 이를 map으로 dp를 한다면 시간이 오래 걸리지만 (visited 체크시 log N)

시간내에 결과값을 얻어낼 수 있습니다. map을 활용하지 않고 배열을 사용하여 수식을 이용하고, 상대적인 수로 치환한다면 더욱 빠른 시간내에 풀이가 가능하리라 보는데 오류를 못 찾아내어 20%에서 틀려 map으로 변경했습니다 ^^;

 

 

 

 

< CODE >

#include <iostream>
#include <queue>
#include <climits>
#include <algorithm>
#include <map>

using namespace std;

struct forQ
{
	int x;
	int y;
	int cnt = 0;
};

queue<forQ> q;
int result = -1;
map<pair<int,int>, bool> dp;

bool isChecked(int a, int b)
{
	return dp[{a,b}];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int A, B, a, b;
	
	cin >> A >> B >> a >> b;
	
	q.push({0,0,0});
	
	while(!q.empty())
	{
		forQ cur = q.front(); q.pop();
		
		if(dp[{cur.x,cur.y}])
			continue;
		
		dp[{cur.x,cur.y}] = true;
		
		if(cur.x == a && cur.y == b)
		{
			result = cur.cnt;
			break;
		}
		
		if(!isChecked(0,cur.y))
			q.push({0,cur.y,cur.cnt + 1});
		if(!isChecked(cur.x,0))
			q.push({cur.x,0,cur.cnt + 1});
		
		if(!isChecked(A,cur.y))
			q.push({A,cur.y,cur.cnt + 1});
		if(!isChecked(cur.x,B))
			q.push({cur.x,B,cur.cnt + 1});
		
		if(cur.x < A && cur.y != 0)
		{
			int amount = min(A - cur.x, cur.y);
			
			if(!isChecked(cur.x+amount,cur.y-amount))
				q.push({cur.x + amount, cur.y - amount, cur.cnt + 1});
		}
		
		if(cur.y < B && cur.x != 0)
		{
			int amount = min(B - cur.y, cur.x);
			
			if(!isChecked(cur.x-amount,cur.y+amount))
				q.push({cur.x - amount, cur.y + amount, cur.cnt + 1});
		}
	}
	
	cout << result << '\n';
	
	return 0;
}

시간 : 488ms

 

태그 : #BOJ 물통 #정올 물통 #KOI 물통 #백준 물통 #14867 물통 풀이