알고스팟 : 시계 맞추기

링크 : https://algospot.com/judge/problem/read/CLOCKSYNC

문제읽기

스위치를 누르면 바뀌는 시계들이 정해져있다.
재귀를 이용해서 최소 스위치 클릭 수를 찾아야겠다.

코드

코드는 책의 코드를 분석하는 것으로 끝내겠다. 책에서 너무 많은 것을 구현해줘서 나는 짜집기밖에 안했기 때문이다.

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

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
const char linked[SWITCHES][CLOCKS + 1] = {
    // 0123456789012345
      "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] % 4 != 0) 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;
}

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) {
        ret = min(ret, cnt + solve(clocks, swtch + 1));
        push(clocks, swtch);
    }
    return ret;
}

int main() {
    int cases;
    cin >> cases;
    for (int cc = 0; cc < (cases); cc++) {
        vector<int> clocks(16, 0);
        for (int i = 0; i < (16); i++)
            cin >> clocks[i];
        int ret = solve(clocks, 0);
        cout << (ret >= INF ? -1 : ret) << endl;

    }
}

분석

cout << (ret >= INF ? -1 : ret) << endl; 최소값을 삼항 연산자를 통해 계산하여 넣을 수 있다는 것을 고려하라.

return areAligned(clocks) ? 0 : INF; 삼항 연산자를 통해 if문을 사용하지 않고 바로 값을 가져올 수 있다는 것을 고려하라.

solve 함수는 앞의 TSP 외판원 문제의 logic을 이용했다는 것을 이해하자.

#define MAX 20

int n;
double dist[MAX][MAX];

double shortestPath(vector<int>& path, vector<bool>& visited, double currentLength) {
    //base case : 모든 도시를 다 돌았을 경우 시작 도시로 돌아가고 종료한다.
    if (path.size() == n) return currentLength + dist[path[0]][path.back()];
    double ret = 987654321; //가장 큰 값으로 초기화
    for (int next = 0; next < n; next++) { //여행 시작~~
        if (visited[next]) continue; //방문했다면 넘어간다. 다음 도시 탐색
        int here = path.back(); //맨 뒤에 있는 값이 현재 있는 위치
        path.push_back(next); //다음 여행할 도시를 넣어준다.
        visited[next] = true; //방문했다는 것을 표시
        //나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다
	//방금 탐색한 도시의 거리까지 포함해서 계속 탐색 w/ 재귀
        double cand = shortestPath(path, visited, currentLength + dist[here][next]);
	//그러고 모든 값을 비교하여 최솟값 찾아내기
        ret = min(ret, cand);
	//재귀라 다시 탐색할 수 있게끔 false로 바꿔준다.
        visited[next] = false;
	//재귀라 다시 탐색하도록 탐색한 도시를 삭제해준다.
        path.pop_back();
    }
    return ret;
}