[BFS] 12886번 돌 그룹

12886번 돌 그룹

 

https://www.acmicpc.net/problem/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을 출력한다.

 

예제 입력

10 15 35

1 1 2

 

예제 출력

1

0

 

해결방법

BFS 탐색을 통해 정답의 경우를 찾는 문제이다

 

N≤500 의 조건을 가지고 있기 때문에 3가지 돌의 크기를 지정한다면

O(500 * 500 * 500) 이므로 125,000,000의 시간이 나온다

따라서 다른 접근 방법이 필요하다고 생각했다

 

⭐️ 솔루션 ⭐️

유에스비 어딨니? 님의 블로그 를 참고하였다

 

만약 돌 그룹의 상태가 15 10 35 라고 한다면 10 15 35 35 10 15 는 다른 상태일까??

아니다! 돌의 개수가 같기 때문에 같은 그룹이다

 

따라서 먼저 돌의 개수를 정렬을 시켜주는게 필요했다

돌의 개수를 각각 입력받으면 구조체 내의 벡터로 push 후 sort 시켜주도록 작성하였다

struct stone {
    vector<int> v;
    
    stone() {}
    stone(int a,int b,int c){
        v.push_back(a);
        v.push_back(b);
        v.push_back(c);
        sort(v.begin(), v.end());
    }
};

 

또한 중복처리를 해줘야했다

bool visited[501][501][501] 은 런타임 에러가 발생했다

그래서 set<string> 을 사용하여 중복처리를 하도록 하였다

정렬 된 돌의 개수를 나열 한 뒤, 개수 사이에 "/" 을 삽입한 문자열을 set 에 저장시켰다

/***** [ A B ] *****/
if(a != b){
    int na = a + a;
    int nb = b - a;
    
    string str = to_string(na) + "/" +  to_string(nb) + "/" + to_string(c);
    if(visited.find(str) == visited.end()){
        q.push(stone(na,nb,c));
        visited.insert(str);
    }
}

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 501
#define INF 987654321
using namespace std;

struct stone {
    vector<int> v;
    
    stone() {}
    stone(int a,int b,int c){
        v.push_back(a);
        v.push_back(b);
        v.push_back(c);
        sort(v.begin(), v.end());
    }
};

int stoneA,stoneB,stoneC;
int max_value;
bool flag;

set<string> visited;

void bfs(){
    queue<stone> q;
    q.push(stone(stoneA,stoneB,stoneC));
    string str = to_string(stoneA) + "/" +  to_string(stoneB) + "/" + to_string(stoneC);
    visited.insert(str);
    flag = false;
    
    while(!q.empty()){
        int a = q.front().v[0];
        int b = q.front().v[1];
        int c = q.front().v[2];
        q.pop();
        
        if(a==b && a==c && b==c){
            flag = true;
            break;
        }
        
        /***** [ A B ] *****/
        if(a != b){
            int na = a + a;
            int nb = b - a;
            
            string str = to_string(na) + "/" +  to_string(nb) + "/" + to_string(c);
            if(visited.find(str) == visited.end()){
                q.push(stone(na,nb,c));
                visited.insert(str);
            }
        }
        
        /***** [ A C ] *****/
        if(a != c){
            int na = a + a;
            int nc = c - a;
            
            string str = to_string(na) + "/" +  to_string(b) + "/" + to_string(nc);
            if(visited.find(str) == visited.end()){
                q.push(stone(na,b,nc));
                visited.insert(str);
            }
        }
        
        /***** [ B C ] *****/
        if(b != c){
            int nb = b + b;
            int nc = c - b;
            
            string str = to_string(a) + "/" +  to_string(nb) + "/" + to_string(nc);
            if(visited.find(str) == visited.end()){
                q.push(stone(a,nb,nc));
                visited.insert(str);
            }
        }
    }
    
    if(flag) cout << 1 << "\n";
    else cout << 0 << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> stoneA >> stoneB >> stoneC;
    max_value = stoneA + stoneB + stoneC;
    
    bfs();
    
    return 0;
}