알고스팟 문제 풀이 CLOCKSYNC

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "CLOCKSYNC"에 대한 풀이입니다.

목차

1. 문제 해결 전략
2. 코드 전문

CLOCKSYNC 문제 URL은 다음과 같습니다.

• CLOCKSYNC URL

문제 해결 전략

제가 이 문제를 해결하기 위해서 체택한 방법은 "무식하게 풀기"입니다. 여기서 문제의 핵심은 시계는 3, 6, 9, 12 만을 가리킨다는 것입니다. 무슨 말이냐면, 첫 번째 테스트케이스를 살펴봅시다. 0~15번까지 시계의 상태는 다음과 같을 것입니다.

모든 시계를 12시를 가리키기 위해서 최소한의 스위치를 누르는 방법은 다음과 같이 1, 2, 3, 4, 5번 시계와 연결된 8번 스위치를 2번 누르는 것입니다. 순서로 쪼개보면 다음과 같이 서술할 수 있겠지요.

 

1. 8번 스위치를 1번 누른다.
2. 8번 스위치를 1번 누른다.

8번 스위치를 1번 눌렀을 때, (순서 1)

8번 스위치를 1번 눌렀을 때, (순서 2)

이제 아래 그림과 같이 모든 시계가 12를 가리키게 되지요.

근데, 최소한의 횟수라는 조건만 제외한다면 이런 방식으로도 모든 시계를 12시를 가리킬 수 있습니다. (1번은 3, 7, 9, 11번 시계와 연결되어 있습니다.)

 

1. 1번 스위치를 1번 누른다.
2. 1번 스위치를 1번 누른다.
3. 8번 스위치를 1번 누른다.
4. 1번 스위치를 1번 누른다.
5. 8번 스위치를 1번 누른다.
6. 1번 스위치를 1번 누른다.

그림으로 살펴보면, 다음과 같습니다.

 

1번 스위치를 1번 눌렀을 때 (순서 1)

1번 스위치를 1번 눌렀을 때 (순서 2)

8번 스위치를 1번 눌렀을 때 (순서 3)

1번 스위치를 1번 눌렀을 때 (순서 4)

8번 스위치를 1번 눌렀을 때 (순서 5)

1번 스위치를 1번 눌렀을 때 (순서 6)

즉 다음의 결과를 얻을 수 있습니다.

위를 보시면, 1번 스위치를 총 4번, 8번 스위치를 2번 눌렀습니다. 이것은 1번 스위치를 0번 누르고 8번 스위치를 2번 누르는 것과 같습니다. 즉, 이 문제에서는 어떤 스위치든 4번 이상 누르는 것은 효과가 없다는 것입니다. 스위치 누른 횟수가 N번이라면, K(N % 4)번 눌렀을 때 상황이 된다는 것이죠. 다음 수식이 성립합니다.

 

"K = N % 4"

 

이것을 제대로 이해했다면 문제 풀기는 쉽습니다. 0~9번까지 스위치를 각각 0번에서 3번까지 모두 눌러보는 것이죠. 그래서 모든 시계가 12시를 가리키는 상황이 되기까지 최소 횟수를 반환하면 됩니다. 우리가 이 문제를 풀기 위한 조각은 다음과 같습니다.

 

1. 스위치 번호에 따른 시계 움직이기
2. 모든 시계가(0~15번까지의 시계들이) 12시를 가리키는지 확인하기
3. 1, 2를 이용하여 모든 스위치를(09번까지의 스위치들을) 03번까지 눌러보기

자 이제 문제를 풀기 위한 퍼즐들을 맞춰봅시다.

 

스위치 번호에 따른 시계 움직이기

먼저 문제 조건에 따른 스위치와 연결된 시계를 표현해봅시다. 스위치의 개수는 10개, 각각 연결된 표는 다음과 같지요.

이를 코드로 표현하면 다음과 같습니다.

 

const int CLOCK_CNT = 16;
const int SWITCH_CNT = 10;

const vector< vector<int>> clockSwitches = {
    { 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 } 
};

 

이제 스위치를 눌렀을 때, 연결된 시계들을 움직여봅시다. 먼저 스위치 번호가 입력으로 되면, 시계들의 상태값을 저장한 배열의 인덱스를 통해 +3을 하면 됩니다. 이 때 중요한 것은 12일 경우, 시계이기 때문에 다시 3을 가리켜야 한다는 것이죠. 코드는 다음과 같습니다.

 

//현재 시계가 가리키는 숫자를 +3씩 올립니다. 만약 12라면, 3을 반환합니다.
int nextClock(int clock) {
    return ( clock == 12 ) ? 3 : (clock + 3);
}

//해당 스위치 번호에 연결된 시계들의 시간을 +3씩 앞으로 땡깁니다.
void push(vector<int>& clocks, int switchNum) {
    for (auto i : clockSwitches[switchNum]) {
        clocks[i] = nextClock(clocks[i]);
    }
}

 

모든 시계가 12시를 가리키는지 확인하기

이제 0~15번까지의 시계가 모두 12시를 가리키는지 확인합시다. 코드는 다음과 같습니다.

 

bool isAllSync(const vector<int>& clocks) {
    for (auto c : clocks) {
        if (c != 12) {
            return false;
        }
    }

    return true;
}

 

모든 스위치를 0~3번까지 눌러보기

사실 상, 문제를 풀기 위한 모든 조각들을 모두 해결하였습니다. 이제 1, 2번 조각을 가지고 무작정 풀기를 시행하면 됩니다. 여기서 중요한 것은 다음 2가지입니다.

 

1. 문제의 조건에 따르면, 스위치는 10개, 즉, switchNum의 10을 넘지 않습니다.
2. 실패 시, -1을 반환해야 합니다. 하지만, 최소 횟수를 구해야 하기 때문에, -1을 반환하면 안됩니다. -1이 최솟값으로 되기 때문입니다.

먼저 2번을 해결하기 위해서는 반환 값을 -1이 아닌 다른 큰 값을 지정하면 됩니다. 지정된 큰 값이 반환될 경우, -1을 출력시키면 되지요. 이 문제에서 최악의 경우는 0~9번 스위치를 모두 3번 누르는 것입니다. 즉, 이 문제에서 최대로 스위치를 누르는 횟수는 30번이 넘지 않습니다.

 

이제 1번 2번을 유의해서 모든 스위치를 0~3번씩 눌러봅시다. 어떻게 그럴 수 있을까요? 이것은 꽤 이야기를 복잡하니 코드 먼저 살펴보도록 하겠습니다.

 

// 스위치를 아무리 눌러도 스위치 개수 * 3 을 넘지 않는다.
const int INF = SWITCH_CNT * 3 + 1; 

int solution(vector<int> clocks, int switchNum) {
    //모든 스위치를 다 눌러봤을 때,
    if (switchNum == SWITCH_CNT) {
        return isAllSync(clocks) ? 0 : INF;
    }

    int ret = INF;

    // 해당 스위치를 0번 눌렀을 때 : 안눌렀을 때
    // 해당 스위치를 1~3번 눌렀을 때 : 시계가 이전보다 3시간씩 움직임
    // 해당 스위치를 4번 이상 눌렀을 때 : (i % 4)번 눌렀을 때와 같음. 즉 0~3만 확인해보면 됨
    for (int i=0; i<4; i++) {
        int tmp = i + solution(clocks, switchNum + 1);
        ret = (ret < tmp) ? ret : tmp;
        push(clocks, switchNum);
    }

    return ret;
}

 

즉, 이 코드는 다음처럼 순회하게 됩니다.

 

1. 0번 스위치를 0번 눌렀을 때, (횟수 = 0)
   1. 1번 스위치를 0번 눌렀을 때, (횟수 = 0)
      1. ...
   2. 1번 스위치를 1번 눌렀을 때, (횟수 = 1)
      1. ...
   3. 1번 스위치를 2번 눌렀을 때, (횟수 = 2)
      1. ...
   4. 1번 스위치를 3번 눌렀을 때, (횟수 = 3)
      1. ...
2. 0번 스위치를 1번 눌렀을 때, (횟수 = 1)
   1. 1번 스위치를 0번 눌렀을 때, (횟수 = 1)
      1. ...
   2. 1번 스위치를 1번 눌렀을 때, (횟수 = 2)
      1. ...
   3. 1번 스위치를 2번 눌렀을 때, (횟수 = 3)
      1. ...
   4. 1번 스위치를 3번 눌렀을 때, (횟수 = 4)
      1. ...
3. 0번 스위치를 2번 눌렀을 때, (횟수 = 2)
   1. ...
4. 0번 스위치를 3번 눌렀을 때, (횟수 = 3)
   1. ...

즉, 이것을 0번에서 9번 스위치까지 순회하고 각 상황에서의 횟수를 비교해서 최소 횟수를 반환하게 됩니다.

코드 전문

다음은 알고리즘 풀이 코드 전문입니다. 위에서 설명하지 않은 main 함수에서 문제의 입력을 다루고 있으니 유의해서 봐주세요! 또한, 이전 절에서 얘기했듯이 -1을 출력하는 상황을 잘 살펴보세요.

 

#include <iostream>
#include <vector>

using namespace std;

const int CLOCK_CNT = 16;
const int SWITCH_CNT = 10;
const int INF = SWITCH_CNT * 3 + 1;

const vector< vector<int>> clockSwitches = {
    { 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 nextClock(int clock) {
    return ( clock == 12 ) ? 3 : (clock + 3);
}

void push(vector<int>& clocks, int switchNum) {
    for ( auto i : clockSwitches[switchNum] ) {
        clocks[i] = nextClock(clocks[i]);
    }
}

bool isAllSync(const vector<int>& clocks) {
    for (auto c : clocks) {
        if (c != 12) {
            return false;
        }
    }

    return true;
}

int solution(vector<int> clocks, int switchNum) {
    if (switchNum == SWITCH_CNT) {
        return isAllSync(clocks) ? 0 : INF;
    }

    int ret = INF;

    for (int i=0; i<4; i++) {
        int tmp = i + solution(clocks, switchNum + 1);
        ret = (ret < tmp) ? ret : tmp;
        push(clocks, switchNum);
    }

    return ret;
}

int main() {
    int C;
    cin >> C;

    if ( !( 0 < C && C <= 30 ) ) {
        cout << "fail: C must between 1 to 30" << endl;
        return 0;
    }

    for (int i=0; i<C; i++) {
        auto clocks = vector<int>(CLOCK_CNT);

        for (int j=0; j<CLOCK_CNT; j++) {
            int N;
            cin >> N;

            if ( !( N == 3 || N == 6 || N == 9 || N == 12 ) ) {
                cout << "fail: N must 3 or 6 or 9 or 12" << endl;
                return 0;
            }

            clocks[j] = N;
        }

        int result = solution(clocks, 0);
        result = (result == INF) ? -1 : result;
        cout << result << endl;
    }

    return 0;
}

 

다음 코드를 제출하면, 2000ms 이내로 통과하는 것을 확인할 수 있습니다. 역시 이 문제도 0ms로 성공하는 사람이 있는 것을 보니 동적 계획법이나 다른 최적화 알고리즘을 통해서 효율성을 올리는 방법이 있는 것 같습니다. 다만, 저는 무작정 풀기 까지만 서술해보겠습니다. 한 번 이 문제의 효율성을 올려보도록 해보세요. 새로운 도전이 될겁니다.