[알고스팟] 시계 맞추기 - 완전 탐색, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

시계 맞추기(링크)

접근 방법

TSP 문제처럼 스위치 10개를 순차적으로 누르며 각 스위치를 3번 누를 때까지 (4번 누르는 것은 안 누르는 것과 같다.) 재귀 호출했다.

실패 원인

이 문제는 TSP처럼 도시의 (스위치의) 방문 순서 (누르는 순서)가 중요하지 않다. (1번 누르고 4번 누르는 것과 4번 누르고 1번 누르는 것은 완전히 동일하므로.) 핵심은 각 스위치당 얼마나 누르는지를 중점으로 재귀호출해야 한다.

C++ 코드

#include<bits/stdc++.h>
using namespace std;

const int INF = 9999, SWITCHES =10, CLOCKS = 16;

const char linked[SWITCHES][CLOCKS+1] = {
    "xxx.............",
    "...x...x.x.x....",
    "....x.....x...xx",
    "x...xxxx........",
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x..",
};

bool areAligned(const vector<int>& clocks){

    for(int i = 0; i < CLOCKS; ++i)
        if(clocks[i] != 12) return false;
    return true;
}

void push(vector<int>& clocks, int swtch){

    for(int clock=0;clock<CLOCKS;++clock)
        if(linked[swtch][clock] == 'x'){
            clocks[clock] += 3;
            if(clocks[clock] == 15) clocks[clock] = 3;
        }
}

int solve(vector<int>& clocks, int swtch){

    if(swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;

    int ret = INF;
    for(int cnt=0;cnt<4;++cnt){ // 0번에서 3번 누르는 경우
        ret = min(ret, cnt + solve(clocks, swtch + 1));
        push(clocks, swtch);
    }
    
    return ret;
}

int main(){

    int caseNum;
    vector<int> answers;
    vector<int> clocks;

    cin >> caseNum;
    while(caseNum-- > 0){

        for(int i = 0; i < CLOCKS; ++i){
            int n;
            cin >> n;
            clocks.push_back(n);
        }

        answers.push_back(solve(clocks, 0));

        clocks.clear();
    }

    for(int i = 0; i < answers.size(); ++i)
        cout << answers[i] << endl;

    return 0;
}