무식하게 풀기(Brute force) - 4. 시계 맞추기

문제 : Synchronizing Clocks (난이도 中)

 

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

 

문제 분석

 

위 문제는 앞서 푼 문제같이 무작정 재귀 호출을 할 수 있는 케이스가 아니다.

최적화 과정이 필요하다.

 

스위치를 누르는 데 있어 순서가 필요없다는 것을 주목하자.

또한 스위치를 4번 누르면 제자리로 돌아온다.

 

따라서 4^10 = 1,048,576 번 검사를 하면 된다.

 

구현

 

 

using namespace std;

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

//스위치가 연결된 경우 'x', 아닌 경우 '.'
const char linked[SWITHCHES][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 (int i = 0; i < clocks.size(); i++)
	{
		if (clocks[i] != 12) return false;
	}
	return true;
}

//swtc번 스위치를 누른다.
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;
		}
	}
}

//10 중 for문이 압축 되는 과정이다. 주목하자.
int solve(vector<int>& clocks, int swtch)
{
	if (swtch == SWITHCHES) 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);
		//4번 누르면 원래 자리로 돌아오기 때문에 따로 추가 작업을 해줄 필요가 없다.
	}

	return ret;
}


int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		vector<int> input_clocks;
		for (int i = 0; i < 16; i++)
		{
			int tmp;
			cin >> tmp;
			input_clocks.push_back(tmp);
		}

		int ans = solve(input_clocks, 0);
		if (ans == INF) ans = -1;
		
		cout << ans << '\n';
	}

	return 0;
}

 

회고

 

다중 for문을 어떻게 압축하느냐에 따라 속도 차이가 크게 나타난다.

할 수 있음 압축하는 것이 좋은 코드인 것 같다.