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

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

12886번: 돌 그룹

BFS를 이용해 푸는 문제입니다.

BFS를 짜는 것 자체는 간단했습니다.

돌이 A, B, C가 존재하니 옮길 수 있는 경우는 3가지입니다.

1. A 와 B

2. A 와 C

3. B 와 C

 

각 경우에서도 X가 큰 경우, Y가 큰 경우가 있으니 총 6가지 경우만 확인하면 됐습니다.

 

방문했던 돌의 크기를 확인하는 방법은 3차원 배열을 이용해 [A][B][C]로 저장하면 편하겠지만, 각 돌이 나올 수 있는 수는 1500까지이니, [1500][1500][1500]칸을 만들어야 합니다. 

따라서 해당 방법보다는 [A + B*10 + C*100]으로 만들어 150000칸만 만들 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int A, B, C;
int check[150001];
typedef struct rock{
    int a, b, c;
}R;
queue<R> q;
    
void AtoB(int a, int b, int c){
    if(a < b){
        if(check[(a+a) + (b-a)*10 + c*100] == 0){
            q.push({a + a, b - a, c});
            check[(a+a) + (b-a)*10 + c*100] = 1;
        }
    }
    else{
        if(check[(a-b) + (b+b)*10 + c*100] == 0){
            q.push({a - b, b + b, c});
            check[(a-b) + (b+b)*10 + c*100] = 1;
        }
    }
}

void AtoC(int a, int b, int c){
    if(a < c){
        if(check[(a+a) + b*10 + (c-a)*100] == 0){
            q.push({a + a, b, c - a});
            check[(a+a) + b*10 + (c-a)*100] = 1;
        }
    }
    else{
        if(check[(a-c) + b*10 + (c+c)*100]){
            q.push({a - c, b, c + c});
            check[(a-c) + b*10 + (c+c)*100] = 1;
        }
    }
}

void BtoC(int a, int b, int c){
    if(b < c){
        if(check[a + (b+b)*10 + (c-b)*100]){
            q.push({a, b + b, c - b});
            check[a + (b+b)*10 + (c-b)*100] = 1;
        }
    }
    else{
        if(check[a + (b-c)*10 + (c+c)*100] == 0){
            q.push({a, b - c, c + c});
            check[a + (b-c)*10 + (c+c)*100] = 1;
        }
    }
}

bool bfs(){
    q.push({A, B, C});
    check[A + B * 10 + C * 100] = 1;
    while(!q.empty()){
        int a = q.front().a;
        int b = q.front().b;
        int c = q.front().c;
        q.pop();
        if(a == b && b == c) return true;
        if(a != b) AtoB(a, b, c);
        if(a != c) AtoC(a, b, c);
        if(b != c) BtoC(a, b, c);
    }
    return false;
}

void solve(){
    if(A == B && B == C) cout << "1";
    else if(bfs()) cout << "1";
    else cout << "0";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> A >> B >> C;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요