[Brute-force] Synchronizing Clocks

#include <iostream>
#include <vector>
#include <algorithm>
 
int clocks[4][4] = {0,};
int switchPushNum[10] = {0,};
std::vector<std::vector<int>> switchToClock = {
    {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}
};
std::vector<std::vector<int>> clockToSwitch(16);
 
void pushSwitch(int switchNum, int direction)
{
    int y = 0, x = 0, tmp = 0;
    for(int i = 0; i < switchToClock[switchNum].size(); i++)
    {
        y = switchToClock[switchNum][i] / 4;
        x = switchToClock[switchNum][i] % 4;
        tmp = clocks[y][x] + direction*3;
        clocks[y][x] = (tmp == 0 ? 12 : (tmp == 15 ? 3 : tmp));
    }
}
 
int to12(int count)                                                             
{
    int ret = 987654321, starty = 0, startx = 0, startNum = 0, switchNum = 0, count2 = 0;
    
    
    
    for(int i = 0; i <4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            if (clocks[i][j] != 12)
            {
                starty = i;
                startx = j;
                break;
            }
            count2++;
        }
    }
    if (count2 == 16) return count;
 
    startNum = starty*4 + startx;
    for(int i = 0; i < clockToSwitch[startNum].size(); i++)
    {
        
        switchNum = clockToSwitch[startNum][i];
        if(switchPushNum[switchNum]+ 1 < 4 )
        {
            switchPushNum[switchNum] +=1;
            pushSwitch(switchNum, 1);
            ret = std::min(to12(count + 1), ret);
            pushSwitch(switchNum, -1);
            switchPushNum[switchNum] -=1;   
        }
    }
 
    return ret;
}
 
int main(void)
{
    int testCase = 0, ret = 0;
    
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < switchToClock[i].size(); j++)
           clockToSwitch[switchToClock[i][j]].push_back(i);
    
    std::cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        for(int j = 0; j < 4; j++)
            for(int k = 0; k < 4; k++)
                std::cin>>clocks[j][k];
        ret = to12(0);
        if(ret == 987654321)
            std::cout<<-1<<std::endl;
        else
            std::cout<<ret<<std::endl;
    }
}

 

 

 

 

1. 완전탐색

    12시가 아닌 시계를 찾고

    그 시계를 움직이는 스위치들 각각의 누르는 경우를 센다.

    (4번 누르면 원상태이므로 3번까지만 누른다.)

 

2. 스위치 -> 시계 배열과 시계 -> 스위치 배열을 만들어 쉽게 접근할 수 있도록 했다

 

3. 12시가 아닌 시계를 찾는게 아니라 

    10개의 스위치들을 0~3번 누르는 각각의 경우의 수에서 

    전체 시계가 12시인 것중 가장 적게 스위치를 누른 경우를 찾으면

    더 빠른 시간 안에 문제를 해결할 수 있다. 

 

Synchronizing Clocks