[완전 탐색] CLOCKSYNC

[1. 문제 재정의 및 추상화]

1. 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계가 연결되어 있다.
2. 한 스위치를 누를때마다 연결된 시계는 3시간씩 앞으로 움직임 (3->6, 6->9, 9->12, 12->3)
3. 모든 시계를 12시로 돌려놓기 위해 스위치를 눌러야 할 최소 횟수를 출력해야 함
4. 불가능 할 경우 -1을 출력

 

[2. 해결 계획]

1. 경우의 수가 아니라 최소 횟수를 계산해야 함
2. 그러나 일단 시작은 완전 탐색에서 시작해보도록
3. 스위치를 누르는 순서는 중요하지 않다?

 

[3. 계획 검증]

1. 동일한 스위치를 4번 누르면 결국 처음 상태와 같아짐.
2. 따라서 완전탐색으로 진행 시 전체 경우의 수는 4^10=1,048,576 으로 완전 탐색으로도 충분해 보임

 

[4. 구현]

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

constexpr const int SWITCHS = 10;
constexpr const int CLOCKS = 16;
const int INF = 987654321;
const int LINKS[SWITCHS][CLOCKS] = {
//         0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
/*00*/    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0},
/*01*/    {0, 0, 0, 1, 0, 0, 0, 1, 0, 1,  0,  1,  0,  0,  0,  0},
/*02*/    {0, 0, 0, 0, 1, 0, 0, 0, 0, 0,  1,  0,  0,  0,  1,  1},
/*03*/    {1, 0, 0, 0, 1, 1, 1, 1, 0, 0,  0,  0,  0,  0,  0,  0},
/*04*/    {0, 0, 0, 0, 0, 0, 1, 1, 1, 0,  1,  0,  1,  0,  0,  0},
/*05*/    {1, 0, 1, 0, 0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  1,  1},
/*06*/    {0, 0, 0, 1, 0, 0, 0, 0, 0, 0,  0,  0,  0,  0,  1,  1},
/*07*/    {0, 0, 0, 0, 1, 1, 0, 1, 0, 0,  0,  0,  0,  0,  1,  1},
/*08*/    {0, 1, 1, 1, 1, 1, 0, 0, 0, 0,  0,  0,  0,  0,  0,  0},
/*09*/    {0, 0, 0, 1, 1, 1, 0, 0, 0, 1,  0,  0,  0,  1,  0,  0} 
};
const int NEXTHOUR[12+1] = {
//  0, 1, 2, 3, 4, 5, 6, 7, 8,  9, 10, 11, 12
    0, 0, 0, 6, 0, 0, 9, 0, 0, 12,  0,  0,  3 
};

void push_switch(std::vector<int>& clocks, const int switch_no)
{
    // 모든 시계에 대해서
    for (int idx = 0; idx < clocks.size(); idx++)
    {
        // 해당 스위치에 연결된 경우
        if (LINKS[switch_no][idx])
        {
            // 시간을 바꿈.
            clocks[idx] = NEXTHOUR[clocks[idx]];
        }
    }
}

int solve(std::vector<int>& clocks, const int switch_no)
{
    // Base Case 1
    if (std::all_of(clocks.begin(), clocks.end(), 
                    [](const int clock){return clock == 12;}))
    {
        return 0;
    }

    // Base Case 2
    // 모든 switch 를 눌렀는데, 모든 시계가 12시가 아님
    if (switch_no == SWITCHS)
    {
        return INF;
    }

    int ret = INF;
    // 현재 스위치를 한번도 누르지 않는 경우 부터
    // 최대 3번까지 누르는 경우를 확인
    for (int push = 0; push < 4; push++)
    {
        const int recursion_ret = solve(clocks, switch_no + 1);
        // 모두 12시로 바뀔 수 있는 경우에 대해서만 ret 값을 업데이트 함.
        // INF 는 전체 경우의 수 보다 큰 값.
        ret = (recursion_ret != INF) ? std::min(ret, push + recursion_ret) : ret;
        // 4번째 실행 시 다시 처음 상태로 되돌아 옴.
        push_switch(clocks, switch_no);
    }

    return ret;
}

int main()
{
    int T;
    std::vector<int> clocks(CLOCKS);

    scanf("%d", &T);
    for (int t = 0; t < T; t++)
    {
        int clock;
        for (int c = 0; c < CLOCKS; c++)
        {
            scanf("%d", &clock);
            clocks[c] = clock;
        }
        const int ret = solve(clocks, 0);
        printf("%d\n", ret == INF ? -1 : ret);
    }
    return 0;
}