[C++] 알고스팟/완전탐색 - Synchronizing Clocks

문제 링크

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

algospot.com :: CLOCKSYNC

 

0번부터 9번까지의 스위치를 0~3번씩 누르는 모든 경우의 수를 완전탐색으로 모든 시계가 12시가 되는 최소 버튼의 수를 구합니다. 스위치를 4번 누르는 것은 한 바퀴를 도는 것이기 때문에 스위치마다 최대 3번 이상은 누르지 않아도 되기 때문입니다.

이 경우 4^10 = 1048576개의 경우의 수가 나오기 때문에 제한 시간안에 모든 경우의 수를 탐색해볼 수 있습니다.

 

 

구현 코드

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int INF=9999, SWITCHES = 10, CLOCKS = 16;
	//10개의 스위치
	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(auto it : clocks){
	if(it != 12){
	return false;
	}
	}
	return true;
	}
	//swtch번 스위치를 push
	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){
	//경우의 수를 모두 탐색했을 때 모든 시계가 12시에 맞춰져있지 않다면 INF를 반환
	if(swtch == SWITCHES)
	return areAligned(clocks) ? 0 : INF;
	int ret = INF;
	//swtch번 스위치를 0번에서 3번까지 누르는 경우를 탐색
	for(int cnt=0;cnt<4;++cnt){
	ret = min(ret, cnt+solve(clocks,swtch+1));
	push(clocks,swtch);
	}
	return ret;
	}
	int main(){
	int test_case;
	cin >> test_case;
	while(test_case--){
	vector<int> clock(16);
	for(int i=0;i<16;i++){
	cin >> clock[i];
	}
	int result = solve(clock,0);
	cout << (result == INF ? -1 : result) << endl;
	}
	}

view raw clocksync.cpp hosted with ❤ by GitHub