종만북 CLOCK C++ 풀이 (코드제공)

1. 문제 설정 확인

적어도 내가 지금까지 본 완전탐색 문제중에 가장 어려운편에 속하는 문제였다. 일단 문제 설정을 요약하자면 다음과 같다 :

1. 시계는 총 16개이다. 각자 3, 6, 9, 12중에 하나로 시간이 맞춰져있다.

2. 스위치는 총 10개이고,, 각각 1개 이상의 시계들과 연결되어 있으며, 한 번 누를때마다 연결된 시계들이 모두 3시간만큼 움직인다.

3. 얼만큼 스위치를 누르던지는 관계 없으며, 모든 시계가 12시를 향하게 해야 한다.

2. 문제 풀이

일단 이 문제는 순서에 따라 스위치를 누른 횟수가 같더라도 결과값이 바뀐다는 사실은 짚고 넘어가자. 따로 중복체크니 뭐니 이런건 당연히 할 필요 없다.

내가 가장 애먹었던 부분이, 도대체 그럼 재귀호출을 언제 종료해야하는 것이였다. 스위치를 무한번 누르면 이거 뭐 호출이 끝나질 않지 않나? 라고 생각하던 차에 책의 힌트를 살짝 참고했다. 여기서 중요한 점은, 어떤 스위치를 얼마만큼 누르던, 3번 이상 스위치를 누르는건, 결국 중복에 지나지 않는다는 것이다. 즉, 4번 누르면 어차피 처음으로 돌아오니 그 후에 100번을 누르던 1000번을 누르던 의미는 없다. 따라서 스위치를 아예 누르지 않는 0번부터 모든 스위치를 최대 3번씩 누르는경우까지만 탐색하면 된다.

난 여기서 크게 함수를 4가지로 나누었다.

1. 입력을 받는 main 함수

2. 재귀호출이 일어나는 solution 함수

3. 시계를 움직이는 rotate 함수

4. 기저조건에서 시계 맞추기의 성공여부를 확인하는 check 함수

여기서 주의해야 할 것은 solution 함수에서 for문이 3번이 아닌, 4번 돈다는 점이다. 4번 도는 이유는 아까 말했다시피, 4번째에 원래 스위치의 상태로 회귀하기 때문이다. 따라서 4번 돌면 일일히 back 함수를 작성하여 회귀처리를 하지 않아도 된다. 정말 짜증나는 시계 문제의 유일한 장점이 아닐까 싶다.

3. 해답 코드

#include <iostream>
#include <vector>
using namespace std;

int INF = 1000000;
int connection[10][16] = {
        {1, 1, 1, 0,},
        {0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 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, 1, 1, 1, 0, 1, 0, 1, 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, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0,}
};

//문제의 스위치-시계 연결의 배열 표현 (순 노가다..)


void rotate(int n, vector<int>& clocks){
    for(int i =0; i < 16; i++){
        if(connection[n][i] == 1){
            clocks[i] += 3;
            if (clocks[i] == 15)
                clocks[i] = 3;
                //원래 12인 경우에는 3시간 더하면 15시가 아닌 3시로 넘어간다.
        }
    }
}

bool check(vector<int>& clocks){
    for(int i = 0; i < 16; i++){
        if (clocks[i] != 12){
            return false;
            // 하나라도 12가 아닌 경우 false를 바로 리턴한다.
        }
    }
    return true;
}

int solution(vector<int>& clocks, int Switch){
    if(Switch == 10)  return check(clocks) ? 0 : INF;
    int result = INF;
    for(int i = 0; i < 4; i++){
        int tmp = solution(clocks, Switch + 1);
        //Switch를 i번 누른채로 Switch + 1, 즉, 다음 스위치 탐색하는 재귀호출 코드다.
        if (tmp < INF) {
            result = min(result, i + tmp);
            //min 함수 호출은 생각보다 느리다. 따라서 tmp가 의미있는 값일때만 사용해주면 속도가 꽤 상승한다.
        }
        rotate(Switch, clocks);
    }
    return result;
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        vector<int> clocks(0);
        for(int j = 0; j < 16; j++){
            int tmp;
            cin >> tmp;
            clocks.push_back(tmp);
        }
        int result = solution(clocks, 0);
        if(result >= INF){
            cout << -1 << endl;
        }
        else {
            cout << result << endl;
        }
    }
}

P.S. 만약 이 문제에서 사용한 재귀호출이 잘 이해가지 않는다면, 재귀호출에 대해 조금 더 공부하고 이 문제를 푸시는게 정신건강에(…) 이롭습니다. 사실 저도 백준을 시작하기 전 알고리즘 처음 잡았을 때 이 책을 샀다가 바로 이 문제에서 하차하고 백준 골드찍고 다시 잡은 케이스랍니다 :)

Source

종만북, 2022.07.22
CLion