[백준/c++] BOJ 12886 - 돌 그룹

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

12886번: 돌 그룹

 

문제 설명

돌들이 세개의 그룹으로 나누어져 있고, 각각의 그룹에는 돌이 A, B, C개 있다.

세 개의 그룹들 중, 크기가 같지 않은 두 그룹을 골라 작은 쪽은 X, 큰 쪽을 Y라고 정한다.

X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

같은 행동을 반복하여 세 그룹의 돌의 개수를 모두 같게 만들 수 있다면 1, 아니면 0을 출력한다.

A, B, C (1 <= A, B, C <= 500)

 

해결

1. 

작은 쪽의 연산은 +X, 큰 쪽의 연산은 -X로 전체 돌의 개수는 연산이 끝나고 유지된다.

따라서 처음 주어진 A, B, C의 합이 3의 배수가 아니면 그룹의 돌을 전부 같은 개수로 만들 수 없다.

또한, 결과적으로 나눠지는 돌의 개수는 각각 sum/3, sum/3, sum/3이 될 것이다.

 

2. 

합이 유지되므로 visited를 3차원으로 만들 필요가 없다. 합을 저장하고, 두 개 그룹의 돌 개수만 안다면 나머지 하나의 돌 그룹의 개수는 sum - A - B로 계산할 수 있다.

마찬가지로 queue에 tuple이 아닌 pair로 두개의 그룹의 돌 개수만 저장한다.

 

3. 

bfs로 연산을 각각 계산하면서 visited 하지 않은 숫자 그룹이면 저장한다.

숫자 세 개 중 두 개를 뽑는 것은, 만들 수 있는 모든 숫자 조합을 해야 하므로,이중 for문을 통해 구현하였다.

bfs가 끝났을 때 visited[sum/3][sum/3]을 리턴한다.

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int visited[10001][10001];
int a, b, c;
int sum = 0;

int bfs() {
	queue<pair<int, int >> q;
	q.push({ a, b });
	visited[a][b] = 1;

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		vector<int> v;
		v.push_back(cur.x); v.push_back(cur.y); v.push_back(sum - cur.x - cur.y);

		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (v[i] < v[j]) {
					int one = v[i] * 2;
					int two = v[j] - v[i];
					if (visited[one][two]) continue;
					visited[one][two] = 1;
					q.push({ one, two });
				}
			}
		}
	}
	return visited[sum / 3][sum / 3];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	cin >> a >> b >> c;
	sum = a + b + c;
	if (sum % 3 != 0) {
		cout << "0";
		return 0;
	}

	cout << bfs();

}