[백준]12886 돌그룹

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

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 로 문제를 풀었다. 우선 세 수의 합이 3의 배수가 아니면 3가지 그룹이 같은 숫자가 될 수 없으므로 그 경우는 제외하고 시작했다. 돌 그룹에서 돌을 어떻게 옮기든 세 숫자의 합은 항상 같으므로 세 숫자 중 두 숫자만 알면 나머지 숫자를 알 수 있기 때문에 visited 배열은 2차원 배열로 하였다.

들어온 숫자 3개를 정렬한 후 queue에 숫자 2개를 push하고 bfs 를 시작한다.

queue 에서 한 원소를 pop 한 다음 나머지 한 숫자를 구한다. 정렬되어있는 세 숫자 중 3그룹->1그룹 / 2그룹->1그룹 / 3->1그룹 을 가는 경우를 나누어 생각했다. 이 경우 옮긴 후 세 숫자를 정렬 한다음에 이 새로운 경우의 수를 visit 했는지 확인하고 visit 하지 않았다면 queue에 그 경우를 push 하고 visited를 1로 바꿔준다. 이렇게 하면 중복된 경우를 여러번 확인하지 않고 한번만 확인 할 수 있다.

이렇게 while 문을 queue 가 비어있지 않을 때 까지 반복한다. 중간에 세 숫자가 같은 경우가 되면 1을 출력하고 함수를 return 하여 끝내고 그렇지 않으면 queue에 push를 하여 반복하는데 queue가 비어있게 된다면 더 이상 확인 할 경우의 수가 없는 것이기 때문에 0을 출력하고 종료한다.

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

using namespace std;

int arr[3];
int visited[1001][1001] = { 0 };
queue<pair<int,int>> bfs;

void check() {
	sort(arr, arr + 3);
	if (!visited[arr[0]][arr[1]]) {
		bfs.push(make_pair(arr[0], arr[1]));
		visited[arr[0]][arr[1]] = 1;
	}
}

void solve() {
	if ((arr[0] + arr[1] + arr[2]) % 3 != 0) {
		printf("0");
		return;
	}
	int sum = arr[0] + arr[1] + arr[2];
	sort(arr, arr + 3);
	bfs.push(make_pair(arr[0], arr[1]));
	while (!bfs.empty()) {
		arr[0] = bfs.front().first;
		arr[1] = bfs.front().second;
		arr[2] = sum - arr[0] - arr[1];	
		if (arr[0] == arr[1] && arr[1] == arr[2]) {
			printf("1");
			return;
		}
		bfs.pop();
		int a = arr[0];int b = arr[1];int c = arr[2];
		arr[0] = a + a; arr[1] = b; arr[2] = c - a;
		check();
		arr[0] = a + a; arr[1] = b - a; arr[2] = c;
		check();
		arr[0] = a; arr[1] = b + b; arr[2] = c - b;
		check();
	}
	printf("0");
	return;
}

int main() {
	cin >> arr[0] >> arr[1] >> arr[2];
	solve();

	return 0;
}

---

딱 문제를 처음 봤을 때는 모든 경우의 수를 확인해야 하나라고 생각을 하고 조금 더 생각해보니 뭔가 규칙이 있는 것 같았다. 제일 먼저 생각했을 때 세 그룹의 숫자가 같으려면 총 합이 3의 배수여야 한다는 것을 확인하였고 예제로 준 문제로 보아 하니 5로 1이 아닌 공약수가 있으면 되지 않을까? 라는 생각을 하였다. 그래서 제출을 해보니 되지 않았다... 왜 안될까 생각을 해봤는데 1 2 3 인 경우 공약수가 1인데도 3->1 그룹을 한다면 2 2 2 가 되는 것이였다! 그래서 이 부분을 더 생각 하지 못하고 그래프 탐색을 하기로 하였다. dfs를 더 많이 사용해봐서 dfs를 할까 했지만 종료 조건이 하나라도 있으면 그만해도 되는데 dfs는 어려울 것 같다는 생각을 했다. 그래서 bfs를 활용하여 풀기로 결정하였다. 그 동안 포스팅한 글들은 다 cin cout 만 쓰는 c언어라고 볼 수 있었는데 이번에는 나름대로 queue 도 쓰고 pair 도 활용해본 것 같아 의미가 있었던 것 같다.