[백준] 12886번 - 돌 그룹 / C++

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세 개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 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을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

vector<int> stone;		// a, b, c 그룹의 돌 개수
set< vector<int> > check;	// 확인된 조합
bool answer;			// 리턴값

void bfs()
{
	queue< vector<int> > q;
	vector<int> tmp(3);
	int i, j;

	// 입력값 추가
	sort(stone.begin(), stone.end());
	check.insert(stone);
	q.push(stone);
	while (!q.empty())
	{
		stone = q.front();
		q.pop();
		// 돌의 개수가 모두 같다면 리턴
		if (stone[0] == stone[1] && stone[1] == stone[2])
		{
			answer = true;
			return;
		}
		// 모든 조합에 대하여 (6가지)
		for (i = 0; i < 2; i++)
		{
			for (j = i + 1; j < 3; j++)
			{
				// 돌의 개수가 같으면 패스
				if (stone[i] == stone[j])
				{
					continue;
				}
				tmp = stone;
				// 작은 쪽은 x + x, 큰 쪽은 y - x
				if (stone[i] < stone[j])
				{
					tmp[j] -= tmp[i];
					tmp[i] *= 2;
				}
				else
				{
					tmp[i] -= tmp[j];
					tmp[j] *= 2;
				}
				// 오름차순 정렬
				sort(tmp.begin(), tmp.end());
				// 확인되지 않은 조합이라면 추가
				if (!check.count(tmp))
				{
					check.insert(tmp);
					q.push(tmp);
				}
			}
		}
	}
}

int main()
{
	int i, tmp;

	for (i = 0; i < 3; i++)
	{
		cin >> tmp;
		stone.push_back(tmp);
	}
	bfs();
	cout << answer << endl;
	return 0;	
}

 

링크

12886번: 돌 그룹

inbdni/Baekjoon