[종만북] - 시계 맞추기(완전탐색)

문제

접근방법

완전탐색 하는 경우, 4^10의 시간이 걸린다.

2^20이므로 1000000정도다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define FASTERINIT ios_base::sync_with_stdio(false); cin_tie(0); cout_tie(0);
#define INF 987654321

const int SWITCHES = 10, CLOCKS = 16;
int C;
vector<int> clocks;
//linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있다.
//linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않다.
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.."
};
//모든 시계가 12시를 가리키고 있는 지 확인한다.
bool areAligned(const vector<int>& clocks) {
    FOR(i, CLOCKS) {
        if (clocks[i] != 12) return false;
    }
    return true;
}

void push(vector<int>& clocks, int swtch) {
    FOR(clock, CLOCKS)
        if (linked[swtch][clock] == 'x') {
            clocks[clock] += 3;
            if (clocks[clock] == 15) clocks[clock] = 3;
        }
}

//clocks: 현재 시계들의 상태
//swtch: 이번에 누를 스위치의 번호
//가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch) {
    if (swtch == SWITCHES) return areAligned(clocks) ? 0 : INF;
    int ret = INF;
    FOR(cnt, 4) {
        ret = min(ret, cnt + solve(clocks, swtch + 1));
        push(clocks, swtch);
    }
    return ret;
}

int main() {

    cin >> C;
    while(C--) {
        clocks = vector<int>(16, 0);
        FOR(i, CLOCKS) {
            cin >> clocks[i];
        }
        int answer = solve(clocks, 0);
        cout << ((answer == INF) ? -1 : answer) << '\n';
    }

    return 0;
}

개선할 점

재귀로 최솟값을 구하는 방식이 인상깊다.

 

나는 시계를 돌린 횟수만큼 저장해서 다음 함수로 넘겨줘야 할 거라고 생각했는데,

그게 아니라. 마지막 함수에서 0을 리턴하고, 그 전 함수에서는 cnt를 더한 값을 더해서 리턴한다.

그리고 그것을 ret와 비교해 더 작은 것을 저장한다.

 

쉬워보이지만, 정교한 방식이다. 

 

다음에 최솟값을 찾는 문제를 마주쳤을 때, 다시 찾아와서 보자.