[백준/c++] 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라는 것은 알겠지만 문제 풀이를 하면서 이상한 점이 한 두가지가 아니다.

어떻게 가지치기를 해줘야 오류가 나지 않을까, 어떻게 해야 재방문을 하지 않을까 꼼꼼히 고민을 해보았는데 visited 배열을 사용해서 계속해서 업데이트를 해주면 되지 않을까 생각했다.

하지만, 3차원 visited를 사용하면 500 500 499 와같은 부분에서 999 500 1 이 나오게되면서 배열의 범위 자체가 너무 방대해지는 문제가 발생하게 되어 2차원 visited배열을 생각해본 결과

어차피? 정렬되어있고, 이동하는 두개의 부분이 같다면 뒤에 하나는 신경쓰지 않아도 되지 않을까?

합은 똑같으니까 라는 생각에 다다랐지만 구현을 하지 못해 나와 비슷한 생각을 한 분의 코드를 따라했다.

https://kibbomi.tistory.com/185 이분의 코드인데 본인보다 설명을 잘하고 구현도 이해하기 쉽게 하셨기 때문에 잘 살펴보면 되겠다.

code

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

#define MAX 1501
using namespace std;

typedef struct{
	
	int x;
	int y;
	int z;
	
}type;

int a,b,c;

queue<type> q;
bool visited[MAX][MAX];

int main(){
	
	cin >> a >> b >> c;
	
	if((a + b + c) % 3 != 0){
		cout << 0; return 0;
	}
	
	q.push({a,b,c});
	
	while(!q.empty()){
		
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().z;
		q.pop();
				
		if(x == y && y == z){
			cout << 1; return 0;
		}

		int a[3];
		a[0] = x; a[1] = y; a[2] = z;
		sort(a, a + 3);
		
		cout << a[0] << " " << a[1] << " " << a[2] << endl;
				
		int next[3];
		if(a[0] != a[1]){
			
			next[0] = a[0] * 2;
			next[1] = a[1] - a[0];
			next[2] = a[2];
			if(!visited[next[0]][next[1]]){
				visited[next[0]][next[1]] = true;
				q.push({next[0],next[1],next[2]});
			}
		}
		
		if(a[0] != a[2]){
			
			next[0] = a[0] * 2;
			next[1] = a[1];
			next[2] = a[2] - a[0];
			if(!visited[next[0]][next[1]]){
				visited[next[0]][next[1]] = true;
				q.push({next[0],next[1],next[2]});
			}
		}
		
		if(a[1] != a[2]){
			
			next[0] = a[0];
			next[1] = a[1] * 2;
			next[2] = a[2] - a[1];
			if(!visited[next[0]][next[1]]){
				visited[next[0]][next[1]] = true;
				q.push({next[0],next[1],next[2]});
			}
		}
	}
	
	cout << 0;
	
	return 0;
}