백준 12886. 돌 그룹

알고리즘 중급 문제 중 611 - BFS(연습)

돌 그룹

1. 간단 설명

---

돌을 세 그룹으로 나누어 A, B, C로 나눈다

모든 그룹의 돌의 수를 같게 하려한다

단계별로 돌을 움직인다

1. 크기가 같지 않은 두 그룹을 선택한다

2. 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 한다

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

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하기

2. 예시

---

예제 1) 10, 15, 35

1단계 : 10, 35 선택하면 `20, 15, 25`
2단계 : 15, 25 선택하면 `20, 30, 10`
3단계 : 10, 30 선택하면 `20, 20, 20`으로 

모두 같은 개수로 만들수 있으므로 1

예제 2) 1 1 2

전체 돌의 개수 4를 3으로 나눈 나머지가 0이 아니므로 불가능하므로 0

예제 3) 2, 3, 4

나머지가 0이라도 불가능한 케이스가 존재한다

예를 들어 2, 3, 4인 경우 어떠한 경우로도 돌을 같은 개수로 나눌 수 없음

계속해서 2, 3, 4 가 나오기 때문에, 무한루프에 빠진다

이를 확인하고 쳐낼 방법이 필요함

이 문제는 아이디어가 떠오르지 않아서 풀이에 실패했다

3. 알고리즘

---

무한루프에 빠지는걸 막기 위해, 해당 돌이 만들어진적이 있는지 체크하는 과정이 필요하다

이를 위해 visited[A][B][C]를 이용한다. 돌의 개수가 A, B, C인 케이스가 만들어진 적 있는지 체크하는 것

그러나 A,B,C 최대값이 500이라고 visited[501][501][501]로 선언해버리면

약 488MB이므로 큐까지 이용해야하는데, 메모리 초과가 발생할 수 있다

이를 방지하기 위해 visited[A][B]만 기록하고 C는 기록하지 않는 방법을 사용한다

어짜피 돌의 총합은 고정되어있고, C는 총합 - A - B로 역산할 수 있기 때문이다

이를 고려하여 알고리즘을 작성해보면

1. 돌 A, B, C를 입력받고 돌의 총 개수를 구한다
2. 만약 총 개수를 3으로 나눈 나머지가 0이 아니라면, 불가능한 케이스이므로 0 출력 후 종료
3. 현재 각 그룹의 돌의 개수를 넣고 BFS를 돌린다 ({A, B}를 넣는다. C는 역산 가능)
	3-1. 큐의 맨 앞에서 현재 그룹당 돌의 개수를 꺼낸다
	3-2. 만약 모든 그룹의 돌의 개수가 같다면 1을 출력 후 종료한다
	3-3. 다르다면, A-B, A-C, B-C 그룹별로 조정한 경우를 계산하고, 이를 큐에 다시 넣는다

필요 변수

• 각 그룹의 돌 개수 int a, b, c, total (a,b,c <= 500, total <= 1500)
• 해당 그룹이 만들어졌는지 체크하기 위한 int visited[1501][1501]
  • 계산 과정에서 500을 초과하는 경우가 발생할 수도 있으므로 500보다 크게 잡아야한다
• BFS에 필요한 큐, 계산에 필요한 임시 변수 등

4. 소스코드

---

#include <iostream>
#include <queue>

using namespace std;

int A, B, C, total;
int visited[1501][1501]; // 방문할 수 있는 숫자의 최대값은 1500임. 500을 넘을 수도 있다

struct node {
	int a;
	int b;
};

int main() {
	cin >> A >> B >> C;
	total = A + B + C;

	if (total % 3 != 0) {
		cout << "0";
		return 0;
	}

	// BFS
	queue<node> qu;
	qu.push({ A, B });
	visited[A][B] = 1;

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		int now_a = now.a;
		int now_b = now.b;
		int now_c = total - now.a - now.b;

		if (now_a == now_b && now_b == now_c) {
			cout << "1";
			return 0;
		}

		// A, B, C 가 각각 다른 경우, 모든 경우에 대해서 개수를 조정하고, 다음 탐색을 위해 큐에 넣는다
		int dx[3] = { now_a, now_a, now_b }; // 각각 {a,b} {a,c} {b,c} 를 비교함 
		int dy[3] = { now_b, now_c, now_c };

		for (int i = 0; i < 3; i++) {
			int na = min(dx[i], dy[i]);
			int nb = max(dx[i], dy[i]);

			nb = nb - na; // Y = Y-X
			na = na + na; // X = X+X 

			if (na < 0 || nb < 0 || na > 1500 || nb > 1500) continue; // 돌이 음수가 되거나, 최대값 초과시
			if (visited[na][nb] == true) continue; // 이미 만들었던 숫자라면 패스

			visited[na][nb] = true;

			qu.push({ na,nb });
			
		}
	}
	cout << "0";

	return 0;
}

1. a와 b만 visited를 이용한 것
2. visited의 최대 크기를 1501까지 잡은 것
3. dx, dy를 이용해 a-b, a-c, b-c를 비교하는 과정

배울게 많은 문제였다