[골드 4] 12886번: 돌 그룹

Original Source: https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

---

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X + X개로, Y에 있는 돌의 개수를 Y - X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

---

풀이

BFS를 사용한다.
돌의 개수를 변경하는 경우는 A ↔ B, A ↔ C, B ↔ C 총 세 가지가 있다. 각각의 경우에 대하여 BFS를 수행하면 된다. 나는 A, B, C 값을 저장하는 구조체와 구조체를 담는 Queue를 선언한 뒤 BFS가 진행됨에 따라 A, B, C 값을 조정하면서 Queue에 삽입하는 방식을 사용했다.

A, B, C의 값에 따라 방문 여부를 저장하는 방문 처리 배열을 만드는데, 이때 돌 하나의 최대 개수가 500이라고 해서 방문 처리 배열의 크기를 500으로 지정하면 안 된다. BFS를 진행하면서 세 그룹의 돌들이 모두 하나의 그룹에 쏠릴 수 있기 때문이다.
다음 Test Case를 생각해보자.

500 500 499

해당 Case에 대해 BFS를 수행한 결과 중 일부를 가져오면 다음과 같다.

…
a : 699   b : 242   c : 558
a : 66     b : 1330 c : 103
a : 225   b : 750   c : 524
a : 1446 b : 23     c : 30
a : 505   b : 54     c : 940
a : 497   b : 772   c : 230
…

따라서 방문 처리 배열의 크기는 최소 1500(500 * 3)으로 설정해야 한다.

돌의 그룹이 세 개라고 해서 방문 처리 배열을 3차원으로 만들면 메모리 초과가 발생한다. BFS를 진행할 때 돌 개수의 총합이 일정하게 유지되므로, 방문 처리 배열을 2차원으로 만들어 A, B의 값에 따른 방문 여부만 저장하면 C = (총합) - A - B 로 C의 값이 단일하게 결정되기 때문에 모든 Case를 고려할 수 있다.

내가 작성한 소스코드

#include <iostream>
#include <queue>
#define MAX 1500

using namespace std;

struct Node {
    int a_;
    int b_;
    int c_;
};

Node stones;
queue<Node> q;
bool is_visited[MAX][MAX];

void input(void) {
    cin >> stones.a_;
    cin >> stones.b_;
    cin >> stones.c_;
    
    return;
}

void save_values(int *arr, int *x, int *y, int *z) {
    arr[0] = (*x);
    arr[1] = (*y);
    arr[2] = (*z);

    return;
}

void restore_values(int *arr, int *x, int *y, int *z) {
    (*x) = arr[0];
    (*y) = arr[1];
    (*z) = arr[2];

    return;
}

void change(int *x, int *y) {
    if ((*x) == (*y)) {
        return;
    }

    if ((*x) < (*y)) {
        (*y) -= (*x);
        (*x) += (*x);
    } else {
        (*x) -= (*y);
        (*y) += (*y);
    }
    
    return;
}

void push_next(int a, int b, int c) {
    if (is_visited[a][b]) {
        return;
    }

    q.push({ a, b, c });
    is_visited[a][b] = true;

    return;
}

void do_bfs(void) {
    int a = stones.a_;
    int b = stones.b_;
    int c = stones.c_;

    if (a == b && b == c) {
        cout << 1 << "\n";
        return;
    }
    
    push_next(a, b, c);

    int temp[3];
    while(!q.empty()) {
        a = q.front().a_;
        b = q.front().b_;
        c = q.front().c_;
        q.pop();

        if (a == b && b == c) {
            cout << 1 << "\n";
            return;
        }

        save_values(temp, &a, &b, &c);
        change(&a, &b);
        if (a == b && b == c) {
            cout << 1 << "\n";
            return;
        }
        push_next(a, b, c);
        restore_values(temp, &a, &b, &c);

        save_values(temp, &a, &b, &c);
        change(&a, &c);
        if (a == b && b == c) {
            cout << 1 << "\n";
            return;
        }
        push_next(a, b, c);
        restore_values(temp, &a, &b, &c);

        save_values(temp, &a, &b, &c);
        change(&b, &c);
        if (a == b && b == c) {
            cout << 1 << "\n";
            return;
        }
        push_next(a, b, c);
        restore_values(temp, &a, &b, &c);
    }

    cout << 0 << "\n";
    return;
}

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

    input();
    do_bfs();
    return 0;
}