[Algospot] 시계 맞추기 (문제 ID : 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 을 출력한다.

---

완전 탐색으로 해결한 문제. 스위치를 누르는 순서는 중요하지 않기 때문에 0번 스위치부터 9번 스위치까지 차례대로 검사하며 각 스위치마다 0 ~ 3 번 씩 스위치를 누른다. 4번 누르면 360도 돌아서 0번과 같은 값을 갖기 때문이다. 각 i번 스위치를 누른 후 다음 i+1번 스위치로 넘어가며 각 단계 마다 모두 12시를 보는 경우가 있는지 확인하기 위해 isAligned 함수를 이용해 정답인 경우가 있을 때 그 때 까지 누른 최소값을 반환한다.

책에선 0, 1, 2, 3번 씩 누르고 1번 더 돌려서 초기화를 하는 방식이었지만 나는 1번 누르고 다시 원상복귀하고 2번 누르고 ... 하는 방식으로 풀었다. 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/CLOCKSYNC.cpp

C++ 코드 :

#include <iostream>
#include <algorithm>
using namespace std;
int C;
int clockState[16];
int swtch[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}
};
bool isAligned()
{
	for (int i = 0; i < 16; i++) {
		if (clockState[i] != 12) return false;
	}
	return true;
}
void pushSwtch(int swtchNum, int pushNum) {
	for (int j = 0; j < pushNum; j++) {
		for (int i = 0; i < 16; i++) {
			if (swtch[swtchNum][i] == 1) {
				clockState[i] += 3;
				if (clockState[i] == 15) clockState[i] = 3;
			}
		}
	}
}
int sync(int currentSwtch)
{
	if (currentSwtch == 10) {
		if (isAligned()) return 0;
		else return 99999;
	}
	int ret = 99999;
	for (int i = 0; i < 4; i++) {
		pushSwtch(currentSwtch, i);	//i번 스위치를 누르고
		ret = min(ret, i + sync(currentSwtch + 1)); // 최소값을 찾는다.
		pushSwtch(currentSwtch, 4-i); //시계를 다시 원상복구
	}
	return ret;
}
int main()
{
	cin >> C;
	while (C--) {
		for (int i = 0; i < 16; i++)
			cin >> clockState[i];
		int res = sync(0);
		if (res == 99999) cout << "-1\n";
		else cout << res << "\n";
	}
}