BOJ 14867 물통

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

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;
}