[c언어/c++] Synchronizing Clocks - 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시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오. 

문제 전체 링크 - https://algospot.com/judge/problem/read/CLOCKSYNC

#include<stdio.h>
#include<memory.h>
int clock[16];
int save[16];
int r;

int min(int a,int b){
 if(a > b) return b;
 else return a;
}

void push(int n){

 switch(n){
 case 0:
  clock[0]+=3;
  clock[1]+=3;
  clock[2]+=3;
  //printf("0\n");
  break;  
 case 1:
  clock[3]+=3;
  clock[7]+=3;
  clock[9]+=3;
  clock[11]+=3;
  //printf("1\n");
  break; 
 case 2:
  clock[4]+=3;
  clock[10]+=3;
  clock[14]+=3;
  clock[15]+=3;
  //printf("2\n");
  break; 
 case 3:
  clock[0]+=3;
  clock[4]+=3;
  clock[5]+=3;
  clock[6]+=3;
  clock[7]+=3;
 // printf("3\n");
  break;
 case 4:
  clock[6]+=3;
  clock[7]+=3;
  clock[8]+=3;
  clock[10]+=3;
  clock[12]+=3;
 // printf("4\n");
  break;
 case 5:
  clock[0]+=3;
  clock[2]+=3;
  clock[14]+=3;
  clock[15]+=3;
 // printf("5\n");
  break;  
 case 6:
  clock[3]+=3;
  clock[14]+=3;
  clock[15]+=3;
 // printf("6\n");
  break; 
 case 7:
  clock[4]+=3;
  clock[5]+=3;
  clock[7]+=3;
  clock[14]+=3;
  clock[15]+=3;
 // printf("7\n");
  break; 
 case 8:
  clock[1]+=3;
  clock[2]+=3;
  clock[3]+=3;
  clock[4]+=3;
  clock[5]+=3;
 // printf("8\n");
  break;
 case 9:
  clock[3]+=3;
  clock[4]+=3;
  clock[5]+=3;
  clock[9]+=3;
  clock[13]+=3;
 // printf("9\n");
  break;
 }

 for(int i = 0 ; i < 16 ; i++)
  if(clock[i] == 15) clock[i] = 3;

 //cnt++;
 /*
 if(clock[0] == 12 && clock[1] == 12 && clock[2] == 12 && clock[3] == 12 &&
  clock[4] == 12 && clock[5] == 12 && clock[6] == 12 && clock[7] == 12 &&
  clock[8] == 12 && clock[9] == 12 && clock[10] == 12 && clock[11] == 12 &&
  clock[12] == 12 && clock[13] == 12 && clock[14] == 12 && clock[15] == 12 ){
   min = (min > cnt) ? cnt : min; 
   cnt = 0;

   for(int i = 0 ; i < 16 ; i++)
    clock[i] = save[i];
 }
 */
}
bool finish(){
 if(clock[0] == 12 && clock[1] == 12 && clock[2] == 12 && clock[3] == 12 &&
  clock[4] == 12 && clock[5] == 12 && clock[6] == 12 && clock[7] == 12 &&
  clock[8] == 12 && clock[9] == 12 && clock[10] == 12 && clock[11] == 12 &&
  clock[12] == 12 && clock[13] == 12 && clock[14] == 12 && clock[15] == 12 ){
   //min = (min > cnt) ? cnt : min; 
   //cnt = 0;

   //for(int i = 0 ; i < 16 ; i++)
    //clock[i] = save[i];

   return 1;
 }
 else return 0;
}
int solve(int n){

 if(n == 10) return (finish() == true) ? 0 : 9999;

 int ret = 9999;
 for(int i = 0 ; i < 4 ; i++){
  ret = min(ret, i+ solve(n+1));
  push(n);
 }

 return ret;
}

int main()
{
 int loop;
 scanf(" %d",&loop);
 for(int l = 0 ; l < loop ; l++){

  r = 0;
  memset(clock,0,sizeof(clock));
  memset(save,0,sizeof(save));

 for(int i = 0 ; i < 16 ; i++){
  scanf(" %d",&clock[i]);
  save[i] = clock[i];
 }
 /*
 ////////////////////////////////
 for(int i = 0 ; i < 16 ; i++)
  printf("%d ",clock[i]);
 printf("\n");
 ////////////////////////////////
 */
 r = solve(0);
 if( r == 9999)
  printf("-1\n");
 else
  printf("%d\n",r);
 /*
 ////////////////////////////////
 for(int i = 0 ; i < 16 ; i++)
  printf("%d ",clock[i]);
 printf("\n");
 ////////////////////////////////
 */
 }
 return 0;

}