[C++]algospot CLOCKSYNC

링크 : https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

문제

그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.

시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.

0	0, 1, 2
1	3, 7, 9, 11
2	4, 10, 14, 15
3	0, 4, 5, 6, 7
4	6, 7, 8, 10, 12
5	0, 2, 14, 15
6	3, 14, 15
7	4, 5, 7, 14, 15
8	1, 2, 3, 4, 5
9	3, 4, 5, 9, 13

시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 개수 C (<= 30) 가 주어진다.
각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.

출력

각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.

예제

입력	출력
2 12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6	2 9

문제 풀이

• 시간은 3, 6, 9, 12시만 있으므로 스위치를 4번 누르게 되면 원래 시간으로 돌아온다. 즉, 10개의 스위치를 누를 수 있는 모든 경우의 수는 4^10이다.
• 스위치의 개수(10개) 만큼 재귀 호출을 통해 스위치를 누를 수 있는 모든 경우를 다 센다. (완전 탐색)

시간 소요한 부분

• 완전 탐색을 하기 위해 재귀 호출을 어떤 식으로 할 지
• Switch 배열에 스위치를 표기하는 부분에서 오타가 있었음

개선 가능한 부분

• 한 스위치를 4번 누르면 시간이 다시 원상복귀된다는 것을 이용하면 재귀 함수가 끝나는 부분에 다시 시계의 시간을 빼줄 필요가 없음

풀이 코드

// 완전 탐색
// 1736ms
#include <iostream>
#include <string.h>
using namespace std;

int Switch[10][16] = {
	{1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
	{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1},
	{1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0},
	{1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
	{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
	{0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1},
	{0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0}
};
int Clock[16];

// 모든 시계의 시간이 12시인지 확인하는 함수
int isAllTwelve() {
	for (int i = 0; i < 16; i++) {
		if (Clock[i] != 12) return 0;
	}
	return 1;
}

int findtwelve(int n, int ret) {
	// basecase
	if (isAllTwelve()) return ret;
	if (n == 10) return -1;			// 스위치는 10번까지만 있음

	// 한 스위치 당 0-3번 누르는 경우 있음
	for (int num = 0; num < 4; num++) {
		for (int j = 0; j < 16; j++) {
			Clock[j] += 3 * Switch[n][j] * num;
			if (Clock[j] > 12) Clock[j] -= 12;
		}

		int res = findtwelve(n + 1, ret + num);
		if (res != -1) return res;

		for (int j = 0; j < 16; j++) {
			Clock[j] -= 3 * Switch[n][j] * num;
			if (Clock[j] < 3) Clock[j] += 12;
		}
	}
	return -1;
}

int main() {
	int C;
	cin >> C;
	for (int i = 0; i < C; i++) {
		for (int j = 0; j < 16; j++) cin >> Clock[j];
		cout << findtwelve(0, 0) << endl;
	}
}