링크 : 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;
}