[종만북 문제] Synchronizing Clocks, 시계 맞추기 (문제 ID : CLOCKSYNC, 난이도 : 중)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 완전 탐색 문제이긴 하지만, 문제를 살짝 변형해서 생각하면 좋다.

---

[종만북 문제] Synchronizing Clocks, 시계 맞추기 (문제 ID : CLOCKSYNC, 난이도 : 중)

이 문제는 .. 여전히 완전탐색으로 풀 수 있다.

다만, 사실 잘 보면 스위치를 누르는 순서는 상관이 없다는 것을 눈치챌 수 있다. 따라서, 스위치 10개를 최대 3번씩 눌러가면서 답을 찾아나가면 된다. 최대 상한은 4^10 이 될 것이다! 😉

#include <iostream>
#include "stdlib.h"
#include <vector>

using namespace std;

#define MINVAL(x, y) (((x) > (y)) ? y : x)
#define MAXVAL(x, y) (((x) > (y)) ? x : y)

int ans;
int clocks[16];

// 사실 30번 이상 스위치를 눌러야 하면, 답이 없는 경우이다.
const int INF = 99999;

// 마지막 스위치에 도달했을 경우
const int LAST = 10;

// 스위치가 이동시키는 시계
vector<vector<int>> switches =
{
	{0, 1, 2},
	{3, 7, 9, 11},
	{4, 10, 14, 15},
	{0, 4, 5, 6, 7},
	{6, 7, 8, 10, 12},
	{0, 2, 14, 15},
	{3, 14, 15},
	{4, 5, 7, 14, 15},
	{1, 2, 3, 4, 5},
	{3, 4, 5, 9, 13}
};

void pressSwitch(int sw)
{
	for (int cl : switches[sw])
		clocks[cl] = (clocks[cl] + 1) % 4;
}

// 모든 시계가 12 시인지 체크
bool allPass()
{
	for (int cl : clocks)
		if (cl != 3)
			return false;
	return true;
}

int sol(int curSw)
{
	// 끝까지 와서 체크한 결과 문제 없으면 답 갱신 시도
	if (curSw == LAST)
	{
		if (allPass())
			return 0;
		return INF;
	}

	// 4 번 돌리면 원위치이므로, 3번까지만 돌리면 된다
	int ans = INF;
	for (int i = 0; i < 4; ++i)
	{
		ans = MINVAL(ans, i + sol(curSw + 1));
		pressSwitch(curSw);
	}

	return ans;
}

void outputHandler()
{
	int ans = sol(0);

	if (ans >= INF)
		ans = -1;
	cout << ans << endl;
}

void inputHandler()
{
	for (int i = 0; i < 16; ++i)
	{
		cin >> clocks[i];
		clocks[i] = (clocks[i] / 3) - 1;
	}
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		outputHandler();
	}

	return 0;
}