https://www.acmicpc.net/problem/14867
간단한 bfs로 풀 수 있는 문제입니다. state의 범위가 크기 때문에 배열이 아닌 set으로 메모이제이션을 해주면 됩니다. 상태가 그렇게 많지 않을 거라는 믿음을 가지고 짜서 맞았는데, 왜 되는지는 잘 모르겠습니다. 믿음을 가지는 게 생각보다 어려운 거 같습니다.
+) cologne 님이 알려주셨습니다. 액션을 한 번 하면 둘 중에 한 물통은 비어있거나 꽉 차 있게 됩니다. 따라서 state는 최대 $2 \times 2 \times 100000$개가 됩니다.
아래는 코드입니다.
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define pii pair<int,int>
using namespace std;
int T, n, a, b, c, d;
int32_t main(void) {
FastIO;
T = 1;
//cin >> T;
while (T--) {
cin >> a >> b >> c >> d;
set<pii> visited;
queue<pair<pii, int>> q;
q.push({ {0, 0}, 0 });
visited.insert({ 0, 0 });
int ans = -1;
while (!q.empty()) {
auto [p, cnt] = q.front();
auto [aa, bb] = p;
q.pop();
if (aa == c && bb == d) {
ans = cnt;
break;
}
//Fill A
int na = a;
int nb = bb;
if (!visited.count({ na, nb })) {
q.push({ {na, nb}, cnt + 1 });
visited.insert({ na, nb });
}
//Fill B
na = aa;
nb = b;
if (!visited.count({ na, nb })) {
q.push({ {na, nb}, cnt + 1 });
visited.insert({ na, nb });
}
//Empty A
na = 0;
nb = bb;
if (!visited.count({ na, nb })) {
q.push({ {na, nb}, cnt + 1 });
visited.insert({ na, nb });
}
//Empty B
na = aa;
nb = 0;
if (!visited.count({ na, nb })) {
q.push({ {na, nb}, cnt + 1 });
visited.insert({ na, nb });
}
//Move water from A to B
int diff = min(b - bb, aa);
na = aa - diff;
nb = bb + diff;
if (!visited.count({ na, nb })) {
q.push({ {na, nb}, cnt + 1 });
visited.insert({ na, nb });
}
//Move water from B to A
diff = min(a - aa, bb);
na = aa + diff;
nb = bb - diff;
if (!visited.count({ na, nb })) {
q.push({ {na, nb}, cnt + 1 });
visited.insert({ na, nb });
}
}
cout << ans << endl;
}
return 0;
}
'알고리즘 문제해결 > BOJ' 카테고리의 다른 글
BOJ 1799 비숍 (0) | 2022.08.12 |
---|---|
BOJ 2671 잠수함식별 (0) | 2022.08.10 |
BOJ 1691 석판 (0) | 2022.08.09 |
BOJ 5821 쌀 창고 (0) | 2022.08.08 |
BOJ 2185 직사각형의 합집합 (0) | 2022.08.07 |