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

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

12886번: 돌 그룹

1. 주의할 점

- BFS, DFS 2가지 방법으로 모두 풀이가 가능하다

- 단계별로 진행했을 때, 현재 돌의 값들이 이전에 나왔는지 검사하는 과정이 필요하다

- 입력 받을 때, 돌의 총합이 3으로 나눠떨어지지 않으면 바로 0을 출력한다

 

2. 구현

- 입력받는 돌들의 값을 지역변수 벡터 V에 저장하고 DFS를 수행한다

- DFS() 함수를 수행하면서 각 원소의 값이 모두 같다면 Avail = True로 전환후, Return한다

- V 벡터를 Sorting하여 가장 큰값에 1501을 곱하고 작은 값을 더하고 Temp에 저장한다

- Set에 Temp 숫자가 저장되어 있다면 Return, 없다면 Set에 추가하고 각 원소들을 비교하여 큰값 - 작은값, 작은값+작은값을 수행한 후, DFS를 다시 수행한다

 

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
set<long long> s;
bool avail = false;

void dfs(vector<int> v) {
	if (avail) return;
	if (v[0] == v[1] && v[1] == v[2]) {
		avail = true;
		return;
	}
	sort(v.begin(), v.end());
	long long temp = (long long)(v[2] * 1501) + v[0];
	if (s.find(temp) != s.end()) return;
	s.insert(temp);
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i == j) continue;
			if (v[i] > v[j]) {
				int tt = v[j];
				v[j] += tt;
				v[i] -= tt;
				dfs(v);
			}
		}
	}
}

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if ((a + b + c) % 3 != 0) cout << 0;
	else {
		vector<int> v;
		v.push_back(a);
		v.push_back(b);
		v.push_back(c);
		dfs(v);
		cout << avail ? 1 : 0;
	}
	return 0;
}