[알고리즘 문제해결 전략] 시계 맞추기

문제출처

• [알고리즘 문제해결 전략1] - 6장 완전탐색 예제
• 소스코드는 구현한 함수의 동작 여부를 관찰하기 위해 본인의 테스트 코드를 추가하여 작성한 결과이다.

문제 설명

• 4x4 배열의 각 원소는 시계 방향을 가리킴(12시, 3시, 6시, 9시)
• 스위치는 10개가 있는데, 각 스위치에 여러개의 원소들이 연결되어 있음
• 모든 배열의 원소를 12시를 가리키도록 맞출때 최소 스위치 누름 횟수를 구한다.
• 모든 원소를 12시로 만들 수 없는 경우 -1을 출력한다.

문제 접근 방향 (bokyoung)

• 시계 바늘의 방향에 따라 12시로 향하기 위해 눌려야 하는 스위치 횟수가 다르다.
  • 12시 -> 0, 4, 8, …
  • 3시 -> 3, 7, 11 …
  • 6시 -> 2, 6, 10 …
  • 9시 -> 1, 5, 9, …
• 각 원소와 연결된 스위치 번호를 나열하고(ex. clock[0][0]와 연결된 스위치가 0,1,2) 그 스위치들을 횟수에 따라 적절히 배분한다.
• 문제는… 조합의 수가 무한하다. 즉, 경우의 수가 너무 많아서 시간 초과는 물론 구현이 복잡하다.

문제 접근 방향 (Solution)

• 문제의 특성을 이용해 적절히 단순화 해야한다.
• 스위치를 누르는 순서는 전혀 중요하지 않다. 중요한 것은 각 스위치를 몇 번이나 누를 것인가 이다.
• 시계는 12시간이 지나면 처음 자리로 돌아온다. 따라서 하나의 스위치를 4번 이상 누르는 것은 의미가 없다.
• 각 스위치를 누르는 횟수는 0~3으로 제한된다! 스위치가 총 10개이므로 최대 경우의 수는 4^10 이다.

구현결과

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
// linked[i][j]='x': i번 스위치와 j번 시계가 연결되어 있다.
// linked[i][j]='.': i번 스위치와 j번 시계가 연결되어 있지 않다.
const char linked[SWITCHES][CLOCKS + 1] = { // NULL 문자 포함
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	"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 areaAligned(const vector<int>& clocks)
{
	for (int clock = 0; clock < CLOCKS; clock++)
		if (clocks[clock] != 12) 
			return false;
	return true;
}
// swtch번 스위치를 누른다.
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;
		}
}
// clocks: 현재 시계들의 상태
// swtch: 이번에 누를 스위치의 번호가 주어질 때,
// 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
// 만약 불가능하다면 INF 이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch)
{
	if (swtch == SWITCHES) // 10개의 스위치를 모두 눌렀을 때 모든 시계가 12시를 향하고 있으면 0을 반환
		return areaAligned(clocks) ? 0 : INF;
	// 이 스위치(swtch)를 0번~3번 누르는 경우에 대해 완전탐색을 진행한다.
	int ret = INF;
	for (int cnt = 0; cnt < 4; cnt++)
	{
		ret = min(ret, cnt + solve(clocks, swtch + 1));
		push(clocks, swtch);
	}
	// push(clocks, swtch)가 4번 호출되었으니 clocks는 원래와 같은 상태가 된다.
	return ret;
}

int main()
{
	int C;
	cin >> C;
	for (int test_case = 0; test_case < C; test_case++)
	{
		vector<int> clocks(16);
		for (int clock = 0; clock < CLOCKS; clock++)
			cin >> clocks[clock];
		int ans = solve(clocks, 0);
		if (ans == INF) cout << "-1" << endl;
		else cout << ans << endl;
	}

	return 0;
}

Test Case

입력
2
12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 
12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6

출력
2
9