시계 맞추기(Synchronizing Clocks)

https://algospot.com/judge/problem/read/CLOCKSYNC

어려웠다.

핵심은 4번 누르는 상황이나 안 누른 상태나 똑같다.

책을 참고해서 구현한 코드와 다른 분의 코드를 참고하여 구현한 코드 2개 첨부한다.

다시 풀어보자.

참고로, AlgoSpot에서 'clock'이라는 변수명을 쓰고 제출하면 컴파일 에러가 뜬다.

<책 참고>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define INF 987654321
 
// linked[i][j] = 1 i번 스위치와 j번 시계가 연결되어 있다
// linked[i][j] = 0 i번 스위치와 j번 시계가 연결되어 있지 않다
 
const int linked[10][16] = {
 
    { 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
 
    { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0 },
 
    { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 },
 
    { 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 },
 
    { 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0 },
 
    { 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 },
 
    { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 },
 
    { 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1 },
 
    { 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
 
    { 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0 }
 
};
 
vector<int> nowClock;
 
// 모두 12시를 가리키고 있는지 검사
bool twelve()
{
    for (auto i : nowClock)
    {
        if (i != 12) return false;
    }
 
    return true;
}
 
// 버튼을 누른다.
void push(int whichButton)
{
    for (int i = 0; i < nowClock.size(); i++)
    {
        if (linked[whichButton][i] == 1)
        {
            nowClock.at(i) += 3;
 
            if (nowClock.at(i) == 15) nowClock.at(i) = 3;
        }
    }
}
 
int solve(int Button)
{
    // 0 ~ 9번 버튼까지 작업 완료.(누른 경우, 안 누른 경우의 작업까지 모두 포함.)
    if (Button == 10)
    {
        return twelve() ? 0 : INF;
    }
    
    int ret = INF;
 
    // 스위치를 0번 누르는 경우부터 3번 누르는 경우까지 모두 시도한다. i번 = 몇 번
    for (int i = 0; i < 4; i++)
    {
        ret = min(ret, i + solve(Button + 1));
        push(Button);
    }
 
    // push(Button)이 4번 호출되었으니, nowClock은 원래와 같은 상태가 된다.
 
    return ret;
}
 
int main(void)
{
    int T = 0, time = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        if (!nowClock.empty()) nowClock.clear();
 
        for (int i = 0; i < 16; i++)
        {
            scanf("%d", &time);
 
            nowClock.push_back(time);
        }
 
        int get = solve(0);
 
        if (get == INF) printf("-1\n");
        else printf("%d\n", get);
    }
    
    return 0;
}

<다른 분의 코드 참고>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define INF 987654321
 
const int button[10][5] = {
    {0, 1, 2, -1, -1},
    {3, 7, 9, 11, -1},
    {4, 10, 14, 15, -1},
    {0, 4, 5, 6, 7},
    {6, 7, 8, 10, 12},
    {0, 2, 14, 15, -1},
    {3, 14, 15, -1, -1},
    {4, 5, 7, 14, 15},
    {1, 2, 3, 4, 5},
    {3, 4, 5, 9, 13}
};
 
int Timer[16];
 
int result = 0;
 
void backtracking(int pos, int cnt)
{
    bool finish = true;
 
    /*for (int i = 0; i < 16; i++)
    {
        printf("%d번 째 시간 = %d\n", i, Timer[i]);
    }

    printf("\n\n");*/
 
    for (int i = 0; i < 16; i++)
    {
        if (Timer[i] % 12 != 0)
        {
            finish = false;
 
            break;
        }
    }
 
    // 모두 12시를 가리키고 있는 경우
    if (finish)
    {
        result = min(result, cnt);
 
        return;
    }
 
    // 모두 12시를 가리키고 있지는 않지만, 버튼을 모두 누른 경우
    if (!finish && pos == 10) return;
    
    // 이미 최솟값인 경우 return.
    if (result <= cnt) return; 
 
    // 안 누른 경우(0번) ~ 3번까지 누른 경우
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            if (button[pos][j] != -1)
            {
                Timer[button[pos][j]] += 3 * i;
            }
        }
 
        backtracking(pos + 1, cnt + i); // 다음 스위치, 누른 횟수
 
        for (int j = 0; j < 5; j++)
        {
            if (button[pos][j] != -1)
            {
                Timer[button[pos][j]] -= 3 * i;
            }
        }
    }
}
 
int main(void)
{
    int T = 0, time = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        result = INF;
 
        memset(Timer, 0, sizeof(Timer));
 
        for (int i = 0; i < 16; i++)
        {
            scanf("%d", &time);
 
            Timer[i] = time;
        }
 
        backtracking(0, 0);
 
        if (result == INF) printf("-1\n");
        else printf("%d\n", result);
    }
    
    return 0;
}