백준_12886_돌그룹

🙋‍♀️ 문제

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

12886번: 돌 그룹

 

🧩 알고리즘

DFS / BFS 알고리즘 둘다 사용 가능 (이번에는 DFS로 풀어봤다.)

 

💡 아이디어

정점: (a,b,c) = 돌의 개수 상태

간선: (a,b,c) → (a´,b´,c´) = 한 단계에서 돌의 이동

전체 돌의 개수는 변하지 않는다는 점을 이용해서 공간복잡도를 줄인다. (dfs 함수의 매개변수로 2개의 돌 그룹만 필요)

 

👩‍💻 코드

#include <iostream>

using namespace std;

int sum;
bool visited[1501][1501];

void dfs(int a, int b) {
	if (visited[a][b]) return;
	visited[a][b] = true;
	int arr[3] = { a,b,sum - a - b };
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (arr[i] < arr[j]) {
				int changed[3] = { a,b,sum - a - b };
				changed[i] += arr[i];
				changed[j] -= arr[i];
				dfs(changed[i], changed[j]);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int a, b, c;
	cin >> a >> b >> c;
	sum = a + b + c;
	if (sum % 3 != 0) {
		cout << 0 << '\n';
		return 0;
	}
	dfs(a, b);
	if (visited[sum / 3][sum / 3]) {
		cout << 1 << '\n';
	}
	else {
		cout << 0 << '\n';
	}
	return 0;
}