[백준] 12886- 돌 그룹(C++)

문제링크: https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

체감 골3 이상이었던 bfs 문제 ㅠㅠ

 

 

접근방식

 

1. dp방식, bfs방식 등이 가능할 것 같았다. 

 

2. 만만한 bfs로 도전

 

만약 a, b, c의 총합이 3으로 딱 나눠떨어지지 않는다면 무조건 결과는 0이다. 

 

1000x1000x1000 배열을 생성하게 되면 메모리 초과이다. 

이때, 총합의 합이 같기 때문에 1000x1000만으로도 a,b,c의 값을 저장할 수 있다는 것을 파악해야 한다.

 

큐에 들어가는 값은 정렬을 하여서 사용한다.

그 이유는 중복을 방지하기 위함과 런타임에러(OutOfBounds)를 방지하기 위함

 

 

 

문제풀이 

 

1.  큐를 사용한 bfs 구현

 

2. y_ar과 x_ar를 통해서 현재 값을 기준으로 탐색해야 하는 값들을 도출

 

 

 

정답코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int visited[1001][1001] = { 0, };
int a, b, c, d = 0;

int bfs() {

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

	while (!que.empty()) {
		int ca = que.front().first;
		int cb = que.front().second;
		int cc = d - ca - cb;
		que.pop();

		if (ca == cb && ca == cc)
			return 1;

		int n_x[3] = { ca,ca,cb };
		int n_y[3] = { cb,cc,cc };

		for (int i = 0; i < 3; i++) {
			int na = n_x[i];
			int nb = n_y[i];
			if (na < nb)
				nb -= na, na += na;
			else if (na > nb)
				na -= nb, nb += nb;
			else
				continue;
			int nc = d - na - nb;

		
			int ra = min(min(na, nb), nc);
			int rb = max(max(na, nb), nc);

			if (visited[ra][rb] == 0) {
				visited[ra][rb] = 1;
				que.push(make_pair(ra, rb));
			}

		}


	}

	return 0;

}

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

	cin >> a >> b >> c;
	d = a + b + c;

	if ((a + b + c) % 3 != 0)
		cout << 0 << endl;
	else
		cout << bfs() << endl;
	

	return 0;
}