[백준 12886] 돌 그룹 (C#, C++) - soo:bak

문제 링크

12886번 - 돌 그룹

설명

세 개의 돌 그룹에서 돌의 개수를 같게 만들 수 있는지 확인하는 문제입니다.

각 단계에서 크기가 다른 두 그룹을 선택하고, 돌의 개수가 적은 그룹 X 와 많은 그룹 Y 를 선택하여,

X 그룹의 돌을 X + X 로 늘리고, Y 그룹의 돌을 Y-X 로 줄이는 작업을 반복하고,

이 과정에서 세 그룹의 돌 수가 모두 같아지는 경우를 탐색해야 합니다.

우선, 세 그룹의 돌의 총합이 3 으로 나누어 떨이지지 않는 경우, 세 그룹의 돌의 수를 같도록 만들 수는 없으므로,

총 합이 3 의 배수가 아니면, 바로 0 을 출력합니다.

이후, 시작 상태에서 BFS 알고리듬을 통해 가능한 모든 돌의 이동을 시도하며 탐색을 진행합니다.

각 상태에서는 세 그룹 중에서 ‘서로 다른 두 그룹’ 을 선택하여 돌을 이동하며,

새로운 상태가 이미 이전에 방문했던 상태가 아닌 경우에 BFS 의 큐에 추가합니다.

BFS 과정 중 세 그룹의 돌 수가 모두 같아지면, 1 을 반환하며 종료합니다.

만약, BFS 과정이 모두 종료되었음에도 세 그룹의 돌 수가 모두 같아지는 경우를 탐색하지 못하였다면 0 을 반환합니다.

---

Code

[ C# ]

namespace Solution {
  class Program {

    private const int END = 1_001;
    private static bool[,] isVisited = new bool[END, END];

    static int BFS(int a, int b, int sum) {
      var queue = new Queue<(int, int)>();
      queue.Enqueue((a, b));
      isVisited[a, b] = true;

      while (queue.Count > 0) {
        var (curA, curB) = queue.Dequeue();
        var curC = sum - curA - curB;

        if (new[] {curA, curB, curC}.All(x => x == curA))
          return 1;

        var pairs = new[] {
          (curA, curB), (curA, curC), (curB, curC)
        };

        foreach (var (first, second) in pairs) {
          var nextA = first;
          var nextB = second;

          if (nextA < nextB) {
            nextB -= nextA;
            nextA *= 2;
          } else if (nextA > nextB) {
            nextA -= nextB;
            nextB *= 2;
          } else continue ;

          var nextC = sum - nextA - nextB;
          var sorted = new[] { nextA, nextB, nextC }.OrderBy(x => x).ToArray();
          var minVal = sorted[0];
          var maxVal = sorted[2];

          if (minVal >= 0 && maxVal < END) {
            if (!isVisited[minVal, maxVal]) {
              isVisited[minVal, maxVal] = true;
              queue.Enqueue((minVal, maxVal));
            }
          }
        }
      }

      return 0;
    }

    static void Main(string[] args) {

      Console.SetIn(new StreamReader(Console.OpenStandardInput()));

      var inputs = Console.ReadLine()!.Split(' ').Select(int.Parse).ToArray();

      var a = inputs[0];
      var b = inputs[1];
      var c = inputs[2];

      var sum = a + b + c;

      Console.WriteLine(sum % 3 != 0 ? 0 : BFS(a, b, sum));

    }
  }
}

[ C++ ]

#include <bits/stdc++.h>
#define END 1001

using namespace std;

typedef pair<int, int> pii;

bool isVisited[END][END];

int bfs(int a, int b, int sum) {
  queue<pii> q;
  q.push({a, b});
  isVisited[a][b] = true;

  while (!q.empty()) {
    int curA = q.front().first,
        curB = q.front().second,
        curC = sum - curA - curB;
    q.pop();

    if (curA == curB && curA == curC)
      return 1;

    int combX[3] = {curA, curA, curB},
        combY[3] = {curB, curC, curC};
    for (int i = 0; i < 3; i++) {
      int nextA = combX[i],
          nextB = combY[i];
      if (nextA < nextB) {
        nextB -= nextA;
        nextA *= 2;
      } else if (nextA > nextB) {
        nextA -= nextB;
        nextB *= 2;
      } else continue ;

      int nextC = sum - nextA - nextB,
          minVal = min({nextA, nextB, nextC}),
          maxVal = max({nextA, nextB, nextC});

      if (minVal >= 0 && minVal < END) {
        if (!isVisited[minVal][maxVal]) {
          isVisited[minVal][maxVal] = true;
          q.push({minVal, maxVal});
        }
      }
    }
  }

  return 0;
}

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

  int a, b, c; cin >> a >> b >> c;
  int sum = a + b + c;

  if (sum % 3) cout << 0 << "\n";
  else cout << bfs(a, b, sum) << "\n";

  return 0;
}