[C++] 알고스팟 - CLOCKSYNC

문제 링크

algospot.com :: CLOCKSYNC

 

 

풀이 )

  0번 스위치를 시작으로 15번 스위치까지 각각 4번씩 눌러가면서 재귀호출을 통해서 모든 경우의 수에 대해서 탐색한다.

  전체 경우의 수가 4^10(≒10^6)이므로 시간초과가 나지 않는다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> push[10] = {
    {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}
};
int clocks[16];

int dfs(int num){
    if(num == 10){
        for(int i = 0; i < 16; ++i){
            if(clocks[i] != 12)
                return 1e7;
        }
        return 0;
    }

    int ret = 1e7;
    for(int i = 0; i < 4; ++i){
        ret = min(ret, i+dfs(num+1));
        int len = push[num].size();
        for(int i = 0; i < len; ++i){
            clocks[push[num][i]] = clocks[push[num][i]]%12+3;
        }
    }
    return ret;
}

int main(void){
    int c;
    cin >> c;
    while(c--){
        for(int i = 0; i < 16; ++i)
            cin >> clocks[i];

            int ans = dfs(0);
            if(ans >= 1e7)
                ans = -1;
            cout << ans << '\n';
    }
}