CLOCKSYNC (중하, p. 168)

동일 스위치를 4번이상 누르게 되는 경우, 한번도 누르지 않은 경우와 같으므로 각각의 스위치는 4번 이상 누르는 경우가 없다.

스위치를 누르는 순서와 상관없이 결과는 같기 때문에 순서는 중요하지 않다.

위의 2가지만 생각할 수 있다면, 모든 스위치를 0~3번 눌러보는 모든 경우의 수는 $4^{10}$가지 존재

따라서 완탐으로 풀면 된다.

책에는 난이도가 ‘중’으로 나와있지만, 중하 정도가 적당할 것 같다.

#include <bits/stdc++.h>
using namespace std;
vector<int> sw[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 ck[16];
int mn_ans;
const int INF = 0x3f3f3f3f;

inline void Rotate(int x, int n) {
    ck[x]+=3*n;
    if(ck[x]>12) ck[x]-=12;
}

inline void RevRotate(int x, int n) {
    ck[x]-=3*n;
    if(ck[x]<=0) ck[x]+=12;
}

void Dfs(int x, int ans) {
    if(x==10) {
        int cnt=0;
        for(int i=0; i<16; i++) {
            if(ck[i]==12) cnt++;
        }
        if(cnt==16) mn_ans = min(mn_ans, ans);
        return;
    }

    for(int i = 0; i < 4; i++) {
        if(i > 0) {
            for(int ck_no : sw[x]) {
                Rotate(ck_no, i);
            }
        }
        Dfs(x+1,ans+i);
        if(i > 0) {
            for(int ck_no : sw[x]) {
                RevRotate(ck_no, i);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        mn_ans = INF;
        for(int i=0; i<16; i++) cin >> ck[i];
        Dfs(0,0);
        if(mn_ans == INF) puts("-1");
        else printf("%d\n", mn_ans);
    }
    return 0;
}