알고스팟 - 시계 맞추기 (CLOCKSYNC) [C++]

 이 문제는 완전 탐색으로 푸는 문제이다. 버튼의 횟수에 초점을 맞추어 재귀를 수행하면 훨씬 수행시간을 줄일 수 있다. 한 버튼을 4번 누르게 되면 처음과 동일하므로 4번 미만까지를 제한을 둘 수 있다. 시간 복잡도의 경우 4^10 ~= 1,000,000 정도가 된다. 따라서 완전 탐색으로 풀 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define NUMBER_OF_CLOCKS 16
#define NUMBER_OF_BUTTONS 10

int answer;
int clocks[NUMBER_OF_CLOCKS];

const vector<int> buttons[NUMBER_OF_BUTTONS] = {
	{0, 1, 2},
	{3, 7, 9, 11},
	{4, 10, 14, 15},
	{0, 4, 5, 6, 7},
	{6, 7, 8, 10, 12},
	{0, 2, 14, 15},
	{3, 14, 15},
	{4, 5, 7, 14, 15},
	{1, 2, 3, 4, 5},
	{3, 4, 5, 9, 13}
};

void push(int buttonIndex) {
	for (int temp : buttons[buttonIndex]) {
		if (clocks[temp] == 12) {
			clocks[temp] = 3;
			continue;
		}
		clocks[temp] += 3;
	}
}

void pop(int buttonIndex) {
	for (int temp : buttons[buttonIndex]) {
		if (clocks[temp] == 3) {
			clocks[temp] = 12;
			continue;
		}
		clocks[temp] -= 3;
	}
}

bool matched() {
	for (int i = 0; i < NUMBER_OF_CLOCKS; i++) {
		if (clocks[i] != 12) {
			return false;
		}
	}

	return true;
}

void solve(int buttonIndex, int count) {
	if (buttonIndex == 10) {
		if (matched()) {
			answer = min(answer, count);
		}

		return;
	}

	for (int i = 0; i < 4; i++) {
		
		for (int j = 0; j < i; j++) {
			push(buttonIndex);
		}
		solve(buttonIndex + 1, count + i);
		for (int j = 0; j < i; j++) {
			pop(buttonIndex);
		}
	}
}

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

	int C;

	cin >> C;

	for (int test = 0; test < C; test++) {
		for (int i = 0; i < NUMBER_OF_CLOCKS; i++) {
			cin >> clocks[i];
		}

		answer = INT32_MAX;
		solve(0, 0);

		if (answer == INT32_MAX) {
			cout << -1 << '\n';
			continue;
		}
		cout << answer << '\n';
	}

	return 0;
}