[알고리즘] Algospot_Synchronizing Clocks

출처 : https://www.algospot.com/judge/problem/read/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 을 출력한다.

정답코드

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

vector<vector<int> > swit({
    vector<int>( { 0, 1, 2 }),
    vector<int>( { 3, 7, 9, 11 }),
    vector<int>( { 4, 10, 14, 15 }),
    vector<int>( { 0, 4, 5, 6, 7 }),
    vector<int>( { 6, 7, 8, 10, 12 }),
    vector<int>( { 0, 2, 14, 15 }),
    vector<int>( { 3, 14, 15 }),
    vector<int>( { 4, 5, 7, 14, 15 }),
    vector<int>( { 1, 2, 3, 4, 5 }),
    vector<int>( { 3, 4, 5, 9, 13 })
});

bool cheakClcok(vector<int>& v)
{
    for(int i=0; i<16; i++)
    {
        if(v[i]%12!=0)  return false;
    }
    return true;
}

void pushSW(vector<int>& v, int pushNum)
{
    for(int i=0; i < swit[pushNum].size(); i++)
    {
        v[swit[pushNum][i]]+=3;
        //if(v[swit[pushNum][i]]==15) v[swit[pushNum][i]]=3;
    }
}

int pushpushbaby(vector<int>& v, int pushNum)
{
    if(pushNum==10) return cheakClcok(v) ? 0 : 9876543;

    int ret = 9876543;

    for(int i=0; i<4; i++)
    {
        ret = min(ret, i+ pushpushbaby(v,pushNum+1));
        pushSW(v,pushNum);
    }

    return ret;
}

int main()
{
    int T;

    cin >> T;

    while(T--)
    {
        int cnt;

        vector<int> v(16,0);

        for(int i=0; i<16; i++)
            cin >> v[i];
        
        cnt = pushpushbaby(v,0);
        
        if(cnt>987654) cout << -1 << endl;
        else    cout << cnt << endl;
    }

    return 0;
}

풀이 및 사고과정

굉장히 어려운 문제였다.
일단 시간초과문제는 똑같은 버튼은 4번 누르면 원래상태와 같아진다는 것을 알았다.
그래서 최소 0번 최대 3번까지만 눌러서 해결했다.
하지만 재귀에 익숙치않아서 현재시각을 넣은 vector을 계속 넘기려하자 오류가 발생했다.
내 아이디어의 한계에 부딪혀 책을 참고하고 문제풀이를 진행하였다.
하다보니 33Line은 그닥 필요가 없어보여 삭제했다.
함수에서 return할 때 삼항연산자를 사용하면 if없이도 return값에 쉽게 변화를 줄 수 있다는 것을 알았고
이와 같은 류의 문제를 많이 봐야 익숙해질 것 같다.