BOJ 12886 · 돌 그룹

알고리즘 분류 : BFS  

A, B, C 돌 그룹에서 돌을 옮기면서 A == B == C 가 되도록 만드는 문제다. A, B, C의 합은 고정되어 있으므로, 두 개의 돌만 사용해도 된다.

• A + B + C의 합을 D라 하자.
• 3개 돌의 수가 같아야 하므로, 3으로 나눴을 때 나누어떨어지지 않으면 만들 수 없는 경우이다.
• 만약 3으로 나누어떨어지면, BFS 탐색을 진행한다.
• A와 B만 사용하면, C는 D-A-B로 나타낼 수 있다.
• (A, B), (A, C), (B, C)를 문제에 주어진 조건에 따라 서로 비교한다.
• 돌 개수가 작은 쪽을 X, 큰 쪽을 Y라 하면, 다음 X 돌은 X+X개이고, 다음 Y 돌은 Y-X개가 된다.
• 마지막 돌을 Z라 하면, Z는 D-X-Y로 나타낼 수 있다.
• 중복된 경우를 제거하기 위해, (X, Y, Z)를 정렬하여 두 값만 사용한다.
• 아래 코드에서는 제일 작은 값과 제일 큰 값을 사용하였다.
• A == B == C가 되면, 1을 출력하고 종료한다.
• 만들 수 없으면 0을 출력한다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int A, B, C, D;
bool check[1000][1000];

void bfs() {
    queue<pair<int, int>> q;
    q.push(make_pair(A, B));
    check[A][B] = true;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second; q.pop();
        int z = D-x-y;
        if (x == y && y == z) {
            printf("1\n");
            return;
        }
        int nx[] = {x, x, y}, ny[] = {y, z, z};
        for (int i=0; i<3; i++) {
            int a = nx[i], b = ny[i];
            if (a < b) b -= a, a += a;
            else if (a > b) a -= b, b += b;
            else continue;
            int c = D-a-b;
            int X = min(min(a, b), c);
            int Y = max(max(a, b), c);
            if (!check[X][Y]) {
                q.push(make_pair(X, Y));
                check[X][Y] = true;
            }
        }
    }
    printf("0\n");
}

void solve() {
    if (D%3) {
        printf("0\n");
        return;
    } else bfs();
}

int main() {
    scanf("%d %d %d", &A, &B, &C);
    D = A+B+C;
    solve();
    return 0;
}

---

Python 3 소스코드

from collections import deque

def bfs():
    q = deque()
    q.append((A, B))
    check[A][B] = True
    while q:
        x, y = q.popleft()
        z = D-x-y
        if x == y == z:
            print(1)
            return
        for a, b in (x, y), (x, z), (y, z):
            if a < b:
                b -= a
                a += a
            elif a > b:
                a -= b
                b += b
            else:
                continue
            c = D-a-b
            X = min(a, b, c)
            Y = max(a, b, c)
            if not check[X][Y]:
                q.append((X, Y))
                check[X][Y] = True
    print(0)

def solve():
    if D % 3:
        print(0)
        return
    else:
        bfs()

A, B, C = map(int, input().split())
D = A+B+C
check = [[False]*D for _ in range(D)]
solve()

---

참고

• 백준 온라인 저지 : BOJ 12886