<Baekjoon> #12886 BFS_Stone Group c++

#12886 돌그룹

처음 문제를 봤을 땐 쉬운 문제라고 생각했는데 생각보다 까다로운 문제같다.

1. bool visited[][]
   우선 세 돌의 개수는 계속 변하므로 돌 세개를 처리하는 벡터를 만드려고 하니 너무 크기가 커졌다. 그런데 어차피 돌 무게 2개가 지정되면 나머지는 자동으로 정해지므로 이차원 벡터로만 만들어도 충분하다.
   visited[a][b]는 돌 무게가 각각 {a,b, 전체 돌 무게-(a+b)}일 때, 이 쌍을 이미 만들어 본 적이 있으면 true, 없으면 false 를 저장한다.
   마지막에는 visited[sum/3][sum/3]이 true인지 false 인지 return 하면된다.

2. queue<pair<int, int>>q
   처음 돌 무게 a,b,c,를 받아와서 a,b 쌍을 큐에 저장하고 int tmp[3]이라는 임시의 공간에 돌 무게쌍을 저장한다.
   돌들의 크기를 비교하여 (X+X, Y-X)의 연산을 수행하고 새로운 돌 무게쌍이 만들어 본 적이 없으면 큐에 삽입해 큐가 빌 때까지 이 과정을 반복한다.

• tmp[]에 돌무게쌍 저장

		int num1 = q.front().first;
		int num2 = q.front().second;
		int tmp[3] = { num1, num2, sum - (num1 + num2) };

• 돌 크기 비교하여 연산 수행

				if (tmp[i] < tmp[j]) {
					int x=tmp[i] * 2;
					int y = tmp[j] - tmp[i];

• 만들어 본 적이 없으면 큐에 삽입

					if (visited[x][y]) continue;
					visited[x][y] = true;
					q.push(make_pair(x,y));

전체 코드

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

const int MAX = 1501;
bool visited[MAX][MAX];

bool bfs(int a, int b, int c) {
	int sum = a + b + c;
	if (sum % 3 != 0) return false;

	queue<pair <int, int>> q;
	q.push(make_pair(a, b));
	visited[a][b] = true;

	while (!q.empty()) {
		int num1 = q.front().first;
		int num2 = q.front().second;
		int tmp[3] = { num1, num2, sum - (num1 + num2) };
		q.pop();
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (tmp[i] < tmp[j]) {
					int x=tmp[i] * 2;
					int y = tmp[j] - tmp[i];

					if (visited[x][y]) continue;
					visited[x][y] = true;
					q.push(make_pair(x,y));
				}
			}
		}
	}
	if (visited[sum / 3][sum / 3]) return true;
		return false;
    }
    int main() {
		memset(visited, false, sizeof(visited));
		int a, b, c;
		cin >> a >> b >> c;
		cout << bfs(a, b, c) << endl;
		return 0;
    }