시계 맞추기

시계 맞추기

4x4개의 격자 형태로 배치된 16개의 시계가 있다. 각 시계들은 3,6,9 혹은 12시를 가리키고 있는데 모든 시계가 12시가 되도록 만들려고 한다.

시계를 조작하는 방법은 10개로 구성된 스위치를 조작하는 방법 뿐이다. 각 스위치들은 최소 3개에서 여러개의 시계와 연결되어 있다. 스위치를 누를 때마다, 해당 스위치와 연결된 시계는 3시간씩 앞으로 움직인다.

모든 시계를 12시로 만드려면 최소한 스위치를 몇 번이나 눌러야 하는지 출력하라.

 

풀이 방법

문제를 있는 그대로 풀려고 하면 완전 탐색으로 불가능하다.

이유는 ?

완전 탐색을 사용하기 위해서는 스위치를 누르는 횟수의 모든 조합을 다 열거할 수 있어야 하는데, 각 스위치를 몇 번 누르는지는 상관없게 된다면 무한대의 조합이 나오게 된다.

 

그래서 스위치에 연결된 어떠한 시계든 스위치를 네 번을 누르게 되면 12시간을 이동하기 때문에 처음 그대로, 즉 하나도 누르지 않은 것과 같다. 따라서 어떠한 스위치는 0번 부터 최대 3번 이상 누를 필요가 없다. 이렇게 되면 10개의 스위치가 있으니 총 4¹⁰ = 1,048,576개의 경우의 수가 나온다.

 

코드 구현

const char linked[10][17] = {
	"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(vector<int>& clocks)
{
	bool ret = true;
	for(auto it : clocks)	
	{
		if(it != 12)	
		{
			ret = false;
			break;
		}
	}

	return ret;
}

// 스위치를 눌러서 3시간씩 돌리는 함수
void push(vector<int>& clocks, int swtch)
{
	for(int clock = 0; clock < 16; ++clock)
	{
		if(linked[swtch][clock] == 'x')
		{
			clocks[clock] += 3;
			if(clocks[clock] == 15)
			{
				clocks[clock] = 3;
			}
		}
	}
}

int solve(vector<int>& clocks, int swtch)
{
	// 기저사례 1. 검증하는 함수 실행
	if(swtch == 10)
	{
		return areAligned(clocks) ? 0 : 9999;
	}

	int ret = 9999;
	for(int i = 0; i < 4; ++i)
	{
		// 스위치를 총 4가지 방식으로 검증
		ret = min(ret, i + solve(clocks, swtch+1));
		push(clocks, swtch);
	}

	return ret;
}

int main()
{
	int t;
	scanf("%d", &t);

	for(int i = 0; i < t; ++i)
	{
		vector<int> input;
		for(int i = 0; i < 16; ++i)
		{
			int num;
			scanf("%d", &num);
			input.push_back(num);
		}

		// 0번째 스위치부터
		cout << solve(input, 0) << endl;
	}

	return 0;
}

 

회고

완전 탐색 문제는 반복 for문으로도 해결 할 수 있다.

하지만 위의 문제 같이 반복문이 10중으로 중첩이 되야 한다면 코드가 복잡해진다.

처음 완전 탐색 문제를 접했을 때는 무조건 단순하게! 반복문을 중첩하면 된다고 생각했지만, 문제를 조금만 복잡하게 꼬아버리면 코드의 흐름을 추적하기가 굉장히 힘들었다.

재귀적으로 구현하는 장점은 코드의 흐름을 추적하기가 굉장히 쉽다. 또한 추상화한 알고리즘 동작을 코드로 구현하기도 간단하다.