[G4] 백준 12886번 돌 그룹 C++ 너비 우선 탐색

리뷰

 

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

문제를 잘못 읽어 접근이 이상했는데 돌의 개수를 두개만 비교해도 된다는 접근을 하게 되었다.

 

 

전역 변수

• a, b, c : 세개의 돌의 크기를 저장할 변수
• total : 세 돌의 크기의 합을 저장할 변수
• v : 방문 정보를 체크하기 위한 변수
• S : 두 돌의 크기를 정의할 구조체

 

함수

1. bfs

bool bfs()

 

너비 우선 탐색을 통해 세 돌의 크기가 같아질 수 있는지 체크하기 위한 함수

1. S타입의 큐 q를 초기화 하고, 세 돌 중 아무 돌이나 두개를 묶어 push해준다.
2. 두 돌의 현재 크기를 기준으로 v배열에 방문 처리를 진행해 준다.
3. q가 빌 때 까지 while 루프를 순회하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
4. 두 돌을 각각 변수 a, b로 저장하고, 변수 c에는 total에서 두 돌의 크기를 뺀 값을 저장해 준다.
5. 기저 조건으로 만약 a, b, c가 모두 동일하다면 true를 반환해 준다.
6. 이후 a, b, c를 각각 비교하며 문제 조건에 맞는 연산 후 방문 처리 되어있지 않다면 방문처리 후 q에 추가해 준다.
7. while 루프가 종료될 때 까지 기저 조건에 도달하지 못한다면 false를 반환해 준다.

 

문제풀이

1. a, b, c 값을 입력 받고, 변수 total에 a, b, c의 합을 저장해 준다.
2. bfs함수를 호출하여 받은 리턴값을 출력해 준다.

 

트러블 슈팅

1. 매 루프 마다 최소 및 최대 크기의 돌만 연산해 주는 줄 알았으나, 크기가 다르다면 모두 진행해 주면 되었다.
2. 구조체에 a, b, c 모두 관리하며 v를 3차원 배열로 관리하려 했으나 돌의 범위가 제한되었다.
3. 두 돌의 크기만 알면 나머지 한 돌의 크기는 알기 때문에 v배열을 2차원으로 접근하니 메모리 문제가 해결되었다.
4. v배열의 크기를 1001 * 1001로 설정해 주고 제출하였으나 OutOfBounds 에러가 출력되었다.
5. 한 돌의 크기가 최대 1500까지 될 수 있으므로 v배열의 크기를 1501 * 1501로 설정해 주니 AC를 받았다.

 

참고 사항

• 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

 

정답 코드

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

int a, b, c, total;
bool v[1501][1501];
struct S {
	int a, b;
};

bool bfs() {
	queue<S> q;
	q.push({ a, b });
	v[a][b] = true;

	while (!q.empty()) {
		S s = q.front(); q.pop();
		int a = s.a, b = s.b, c = total - s.a - s.b;
		if (a == b && b == c) return true;

		int abc[3] = { a, b, c };
		for (int i = 0; i < 2; ++i) {
			int n1 = abc[i];
			for (int j = i + 1; j < 3; ++j) {
				int n2 = abc[j];
				if (n1 != n2) {
					if (n1 > n2) swap(n1, n2);
					n2 -= n1;
					n1 *= 2;
					//cout << n1 << " " << n2 << " " << total - n1 - n2 << "\n";
					if (v[n1][n2]) continue;
					v[n1][n2] = true;
					q.push({ n1, n2 });
				}
			}
		}
	}
	return false;
}

int main() {
	cin >> a >> b >> c;
	total = a + b + c;
	cout << bfs();
}