[백준 2251] 물통 (C#, C++) - soo:bak

문제 링크

2251번 - 물통

설명

세 물통에서 물을 옮기며 첫 번째 물통이 비었을 때 세 번째 물통에 담길 수 있는 모든 양을 구하는 문제입니다.

접근법

가능한 모든 상태를 방문해야 하므로 BFS로 세 물통의 물 양을 탐색합니다.

각 상태에서 여섯 가지 붓기 조합을 진행해 새 상태를 큐에 넣습니다.

첫 번째 물통이 0인 상태의 세 번째 물통 값을 기록하고, 방문 배열로 중복 탐색을 막습니다.

이후, 탐색이 끝나면 기록한 값을 정렬해 출력합니다.

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var cap = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
    var capA = cap[0];
    var capB = cap[1];
    var capC = cap[2];
    var visited = new bool[201, 201, 201];
    var q = new Queue<(int a, int b, int c)>();
    var res = new List<int>();
    q.Enqueue((0, 0, capC));

    while (q.Count > 0) {
      var (a, b, c) = q.Dequeue();
      if (visited[a, b, c]) continue;
      visited[a, b, c] = true;
      if (a == 0) res.Add(c);

      var move = Math.Min(a, capB - b);
      q.Enqueue((a - move, b + move, c));
      move = Math.Min(a, capC - c);
      q.Enqueue((a - move, b, c + move));
      move = Math.Min(b, capA - a);
      q.Enqueue((a + move, b - move, c));
      move = Math.Min(b, capC - c);
      q.Enqueue((a, b - move, c + move));
      move = Math.Min(c, capA - a);
      q.Enqueue((a + move, b, c - move));
      move = Math.Min(c, capB - b);
      q.Enqueue((a, b + move, c - move));
    }

    res.Sort();
    Console.WriteLine(string.Join(' ', res));
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int capA, capB, capC;
  if (!(cin >> capA >> capB >> capC)) return 0;
  bool visited[201][201][201] = {};
  queue<tuple<int,int,int>> q;
  vector<int> res;
  q.push({0, 0, capC});

  while (!q.empty()) {
    auto [a, b, c] = q.front(); q.pop();
    if (visited[a][b][c]) continue;
    visited[a][b][c] = true;
    if (a == 0) res.push_back(c);

    int move;
    move = min(a, capB - b);
    q.push({a - move, b + move, c});
    move = min(a, capC - c);
    q.push({a - move, b, c + move});
    move = min(b, capA - a);
    q.push({a + move, b - move, c});
    move = min(b, capC - c);
    q.push({a, b - move, c + move});
    move = min(c, capA - a);
    q.push({a + move, b, c - move});
    move = min(c, capB - b);
    q.push({a, b + move, c - move});
  }

  sort(res.begin(), res.end());
  res.erase(unique(res.begin(), res.end()), res.end());
  for (size_t i = 0; i < res.size(); i++) {
    if (i) cout << " ";
    cout << res[i];
  }
  cout << "\n";

  return 0;
}