CLOCKSYNC(시계맞추기)

(출처) https://www.algospot.com/judge/problem/read/CLOCKSYNC

알고리즘 코드 로직 안에서 자꾸 경우의 수를 세려고 하니깐 사고과정이 끝없이 복잡해지고 어렵게 된다는 걸 느낌. 완전탐색 문제를 공략하고자 한다면 한번 코드와 떨어져서 대략적인 경우의 수를 먼저 생각하고 진행하는 게 나은 것 같다. 해당 문제는 총 10개의 스위치에서, 각 스위치마다 총 4개의 경우중에(0번,1번,2번,3번) 어떤 것을 선택하게 할 것인지를 고르는 문제로 4^10번의 재귀가 필요하며 재귀 1번당 총 26번의 반복문을 돌게되니 4^10 x 26 = 대략 3천만 번의 반복으로 풀 수 있게 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <time.h>

using namespace std;
vector<vector<int>> clockSwitch = { {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} };
vector<int> path;
int INF = 99999999;


int clocksync(int * clockCase) {
	int ret = INF;
	//기저사례
	if (path.size() == 10) {
		int count = 0;
		int temp_clock[16];
		copy(clockCase, clockCase + 16, temp_clock);

		for (int i = 0; i < 10; i++) {
			if (path[i] == 0) continue;
			for (auto iter = clockSwitch[i].begin(); iter != clockSwitch[i].end(); iter++) temp_clock[*iter] = (temp_clock[*iter] + path[i]) % 4;
			count += path[i];
		}

		for (int i = 0; i < 16; i++) {
			if (temp_clock[i] != 0) return ret;
		}
		return count;
	}

	for (int j = 0; j < 4; j++) {
		path.push_back(j);
		ret = min(ret,clocksync(clockCase));
		path.pop_back();
	}

	return ret;
}

int main() {
	clock_t start, end;
	double result;
	int testcase;
	scanf("%d", &testcase);

	for (int i = 0; i < testcase; i++) {
		int clockCase[16];
		getchar();
		char input[50];
		int index = 0;
		scanf("%[^\n]", input);
		char * p = strtok(input, " ");
		while (p != NULL) {
			switch (*p) {
				case '1': clockCase[index] = 0; break;
				case '3': clockCase[index] = 1; break;
				case '6': clockCase[index] = 2; break;
				case '9':clockCase[index] = 3;
			}
			p = strtok(NULL," ");
			index++;
		}
		start = clock();
		int ret = clocksync(clockCase);
		if (ret == INF) ret = -1;
		printf("%d\n", ret);
		//end = clock();
		//result = (double)(end - start);
		//printf("%f", result);
	}

	return 0;
}