백준 12886: 돌 그룹 (C++)

접근

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

12886번: 돌 그룹

처음에는 DFS나 BFS를 이용하고, set을 이용해 중복되지 않도록 A, B, C를 저장하고 탐색하였지만 짐작대로 시간초과되었다. 시간을 단축할 수 있는 방법으로 두가지를 적용하여 문제를 해결할 수 있었다.

1. 숫자를 저장하는데 있어서 3개의 숫자를 set으로 저장하지 않고 두개만 저장하였다. 숫자 두개만 저장하여도 나머지 한개는 세 숫자의 sum - A - B로 결정할 수 있다.
2. set을 사용하여 새로운 숫자가 나올 때 set을 탐색하지 않고 배열 visited[1501][1501] 을 이용하여 두 개의 숫자가 이미 나왔었는지를 저장해주었다.

코드

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

#define endl '\n'

int A, B, C;
int visited[1501][1501];

int Solve() {
    int sum = A + B + C;
    if (sum % 3 != 0) {
        // 세 숫자의 합이 3의 배수가 아닐 경우, 동일한 숫자로 만들기 불가능
        return 0;
    }
    queue<pair<int, int>> Q;
    Q.push(make_pair(A, B));
    visited[A][B] = 1;
    int a, b;

    while (!Q.empty()) {
        a = Q.front().first;
        b = Q.front().second;
        int tmp[3] = {a, b, sum - a - b};
        Q.pop();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (tmp[i] < tmp[j]) {
                    int num1 = tmp[i] * 2;
                    int num2 = tmp[j] - tmp[i];
                    if (visited[num1][num2]) continue;
                    visited[num1][num2] = 1;
                    Q.push(make_pair(num1, num2));
                }
            }
        }
    }
    return visited[sum / 3][sum / 3];
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> A >> B >> C;

    cout << Solve() << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!