[알고스팟/C,C++] CLOCKSYNK: Synchronizing Clocks

www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

재귀 호출을 통해 완전 탐색을 구현하는 것만으로 해결이 가능한 문제입니다.

int clocks[CLOCK_CNT];
int* switches[SWITCH_CNT]{
    new int[3]{0, 1, 2},
    new int[4]{3, 7, 9, 11},
    new int[4]{4, 10, 14, 15},
    new int[5]{0, 4, 5, 6, 7},
    new int[5]{6, 7, 8, 10, 12},
    new int[4]{0, 2, 14, 15},
    new int[3]{3, 14, 15},
    new int[5]{4, 5, 7, 14, 15},
    new int[5]{1, 2, 3, 4, 5},
    new int[5]{3, 4, 5, 9, 13}
};
int len[SWITCH_CNT]{ 3, 4, 4, 5, 5, 4, 3, 5, 5, 5 };
int res = -1, cmp;

void press(int num, int cnt, int direction)
{
    for (int i = 0; i < len[num]; i++) {
        int snum = switches[num][i];
        clocks[snum] = (clocks[snum] + direction * cnt - 1) % 12 + 1;
        if (clocks[snum] <= 0) clocks[snum] += 12;
    }
}

먼저 스위치를 누르는 함수입니다. 해당 스위치에 연결된 시계가 3시간 뒤로 돌아가도록 만들면 되며, 크게 어려운 부분은 없습니다.

bool success(void)
{
    for (int i = 0; i < CLOCK_CNT; i++) {
        if (clocks[i] != 12) return false;
    }
    return true;
}

모든 시계가 12시를 가리키면 true를 반환하는 함수입니다.

void sync(int num)
{
    if (num == SWITCH_CNT) {
        if (success() && (res == -1 || cmp < res)) res = cmp;
        return;
    }
    for (int i = 0; i < 4; i++) {
        press(num, i, 3);
        cmp += i;
        sync(num + 1);
        press(num, i, -3);
        cmp -= i;
    }
    return;
}

스위치를 눌러보며 모든 시계가 12시를 가리키는지 탐색하는 함수입니다. 재귀 호출로 구현하였고 모든 스위치 번호(0~9번)를 누르면 모든 시계가 12시를 가리키는지 확인하고 결괏값을 갱신합니다. 0부터 3까지 4번 도는 반복문이 총 10번 중첩되어있는 구조로 대략 4^10번 반복문이 돈다고 생각하시면 됩니다. 반복문에 따라 눌러지는 스위치는 아래 표와 같습니다.

트리 형태로 나타내보면 위의 그림과 같은 순서(깊이 우선 탐색)로 순회하게 되는데, 첫 번째 노드는 0번 스위치, 두 번째 노드는 1번 스위치를 의미합니다.

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	1
0	0	0	0	0	0	0	0	0	2
0	0	0	0	0	0	0	0	0	3
0	0	0	0	0	0	0	0	1	0
0	0	0	0	0	0	0	0	1	1

표로 나타내보면 이렇습니다.

#include<iostream>

using namespace std;

#define CLOCK_CNT 16
#define SWITCH_CNT 10

int clocks[CLOCK_CNT];
int* switches[SWITCH_CNT]{
    new int[3]{0, 1, 2},
    new int[4]{3, 7, 9, 11},
    new int[4]{4, 10, 14, 15},
    new int[5]{0, 4, 5, 6, 7},
    new int[5]{6, 7, 8, 10, 12},
    new int[4]{0, 2, 14, 15},
    new int[3]{3, 14, 15},
    new int[5]{4, 5, 7, 14, 15},
    new int[5]{1, 2, 3, 4, 5},
    new int[5]{3, 4, 5, 9, 13}
};
int len[SWITCH_CNT]{ 3, 4, 4, 5, 5, 4, 3, 5, 5, 5 };
int res = -1, cmp;

bool success(void)
{
    for (int i = 0; i < CLOCK_CNT; i++) {
        if (clocks[i] != 12) return false;
    }
    return true;
}

void press(int num, int cnt, int direction)
{
    for (int i = 0; i < len[num]; i++) {
        int snum = switches[num][i];
        clocks[snum] = (clocks[snum] + direction * cnt - 1) % 12 + 1;
        if (clocks[snum] <= 0) clocks[snum] += 12;
    }
}

void sync(int num)
{
    if (num == SWITCH_CNT) {
        if (success() && (res == -1 || cmp < res)) res = cmp;
        return;
    }
    for (int i = 0; i < 4; i++) {
        press(num, i, 3);
        cmp += i;
        sync(num + 1);
        press(num, i, -3);
        cmp -= i;
    }
    return;
}

int main(void)
{
    int c; cin >> c;
    
    for (int i = 0; i < c; i++) {
        for (int j = 0; j < CLOCK_CNT; j++) {
            cin >> clocks[j];
        }
        sync(0);
        cout << res << "\n";
        res = -1;
    }

    return 0;
}

완전 탐색을 구현할 줄 모르면 풀기 힘든 문제입니다. 해당 코드로 2252ms의 수행 시간이 걸렸는데, 역시 고수 개발자 선배님들의 수학적으로 접근(연립방정식을 사용)한 엄청 빠른(0ms) 답안들이 즐비합니다.. 다음에 풀어볼 땐 해당 방법을 통해 풀어봐야겠습니다.