알고리즘 문제해결/BOJ

BOJ 14867 물통

havana723 2022. 8. 10. 17:34

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

 

14867번: 물통

표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최

www.acmicpc.net

 

간단한 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