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

문제 링크 : https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

이 문제에서 핵심 요소는 이미 거쳐갔었던 돌의 갯수들을 어떻게 skip하느냐이다.

즉, 방문했던 곳은 재방문하지 않는다는 BFS와 DFS의 기본 사항을 어떻게 지키느냐가 관건인데, 나는 다음과 같은 방법을 사용했다.

돌 그룹 3개중 갯수를 바꿀 수 있는 그룹은 2개 뿐이다. 

때문에 2개의 돌 그룹의 갯수들을 문제의 요구대로 먼저 갯수를 변경해준 뒤, 만약 변경된 갯수들이 이미 거쳐갔었던 갯수의 조합이라면 큐에 삽입하지 않는 구조이다.

 

세세한 구조는 아래 설명을보며 이해해보자. 

 

문제 풀이는 다음과 같다.

1. 방문할 수 있는 숫자의 최대값은 1500이다. 때문에 bool문 [1501][1501] 크기의 배열을 먼저 만들어준다.

bool ch[1501][1501];

2. 값을 입력받고 초기에 입력받은 값들은 이미 방문했다고 표시를 해준다.

void check(int a, int b, int c){
    ch[a][b] = true;
    ch[b][a] = true;
    ch[b][c] = true;
    ch[c][b] = true;
    ch[a][c] = true;
    ch[c][a] = true;
}

. . .

// main 함수 내부

    int a, b, c, aa, bb, cc;
    cin >> a >> b >> c;
    check(a,b,c);
    queue<pair<pair<int, int>, int>> q;
    q.push({ {a,b},c });

3. 만약 입력받은 3가지 숫자의 합 % 3이 0이 아닐 경우, 무슨 짓을 해도 세 숫자의 크기를 동일하게 만들 수 없다. 

3가지 숫자의 합 % 3이 0인 경우에만 BFS를 진행해준다. 먼저 아래 코드를 대략적으로 훑고 단계별로 하나씩 이해해보자.

    if ((a + b + c) % 3 == 0) {
        while (!q.empty()) {
            aa = q.front().first.first;
            bb = q.front().first.second;
            cc = q.front().second;
            q.pop();
            if (aa == bb && bb == cc) { // 1
                cout << 1 << "\n";
                exit(0);
            }
            if (aa != bb && aa<=1000 && bb<=1000) { // 2
                a = min(aa, bb);
                b = max(aa, bb);
                c = cc;
                b -= a;
                a += a;
                if (!ch[a][b]&&!ch[b][a]) {
                    ch[a][b] = true;
                    ch[b][a] = true;
                    q.push({ { a,b }, c });
                }
            }
            if (aa != cc && aa<=1000 && cc<=1000) { // 3
                a = min(aa, cc);
                c = max(aa, cc);
                b = bb;
                c -= a;
                a += a;
                if (!ch[a][c]&&!ch[c][a]){
                    q.push({ { a,b }, c });
                    ch[a][c] = true;
                    ch[c][a] = true;
                }
            }
            if (bb != cc && bb<=1000 && cc<=1000) { // 4
                a = aa;
                b = min(bb, cc);
                c = max(bb, cc);
                c -= b;
                b += b;
                if (!ch[b][c]&&!ch[c][b]){
                    q.push({ { a,b }, c });
                    ch[b][c] = true;
                    ch[c][b] = true;
                }
            }
        }
    }

(1) 3개의 숫자가 모두 동일할 경우, 1을 출력하고 종료한다.

(2) 만약 aa와 bb의 값이 동일하지 않고, 동시에 두 숫자 모두 1000이하일 경우에 해당 조건식을 진행한다.

중요한 점은 두 숫자 모두 1000이하여야 한다는 점이다. 어차피 각 숫자의 최대값은 500이기 때문에, X+X와 Y-X라는 조건식을 진행하기 이전의 숫자들의 최대값은 1000을 넘을 수 없다.

문제에서 요구하는 X+X, Y-X의 조건을 진행해준 뒤, 해당 숫자들을 방문하지 않았을 경우에만 방문 표시를 해준 뒤 큐에 삽입해준다.

(3) 만약 aa와 cc의 동일하지 않을 경우 해당 조건식을 진행한다. 나머지 상세사항은 (2)번과 같다.

(4) 만약 bb와 cc가 동일하지 않을 경우 해당 조건식을 진행한다. 나머지 상세사항은 (3)번과 같다.

 

4. 큐를 빠져나왔을 경우 세가지 숫자를 동일하게 만들지 못한다는 의미이므로 0을 출력한다.

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

bool ch[1501][1501];

void check(int a, int b, int c){
    ch[a][b] = true;
    ch[b][a] = true;
    ch[b][c] = true;
    ch[c][b] = true;
    ch[a][c] = true;
    ch[c][a] = true;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int a, b, c, aa, bb, cc;
    cin >> a >> b >> c;
    check(a,b,c);
    queue<pair<pair<int, int>, int>> q;
    q.push({ {a,b},c });
    if ((a + b + c) % 3 == 0) {
        while (!q.empty()) {
            aa = q.front().first.first;
            bb = q.front().first.second;
            cc = q.front().second;
            q.pop();
            if (aa == bb && bb == cc) {
                cout << 1 << "\n";
                exit(0);
            }
            if (aa != bb && aa<=1000 && bb<=1000) {
                a = min(aa, bb);
                b = max(aa, bb);
                c = cc;
                b -= a;
                a += a;
                if (!ch[a][b]&&!ch[b][a]) {
                    ch[a][b] = true;
                    ch[b][a] = true;
                    q.push({ { a,b }, c });
                }
            }
            if (aa != cc && aa<=1000 && cc<=1000) {
                a = min(aa, cc);
                c = max(aa, cc);
                b = bb;
                c -= a;
                a += a;
                if (!ch[a][c]&&!ch[c][a]){
                    q.push({ { a,b }, c });
                    ch[a][c] = true;
                    ch[c][a] = true;
                }
            }
            if (bb != cc && bb<=1000 && cc<=1000) {
                a = aa;
                b = min(bb, cc);
                c = max(bb, cc);
                c -= b;
                b += b;
                if (!ch[b][c]&&!ch[c][b]){
                    q.push({ { a,b }, c });
                    ch[b][c] = true;
                    ch[c][b] = true;
                }
            }
        }
    }
    cout << 0 << "\n";
    return 0;
}

이 문제는 어차피 최소 횟수가 아닌 가능 여부만을 따지고 있으므로, DFS로도 접근이 가능하다.