[알고리즘] 완전탐색(CLOCKSYNC)

algospot.com :: CLOCKSYNC

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
queue<int> answer;

const int button[10][5] = {
	{0, 1, 2, -1, -1},
	{3, 7, 9, 11, -1},
	{4, 10, 14, 15, -1},
	{0, 4, 5, 6, 7},
	{6, 7, 8, 10, 12},
	{0, 2, 14, 15, -1},
	{3, 14, 15, -1, -1},
	{4, 5, 7, 14, 15},
	{1, 2, 3, 4, 5},
	{3, 4, 5, 9, 13}
};
int myClock[16] = {0, };
int level;
int maxLevel;

// 버튼을 누르고 clock의 원소를 변경하는 도구
void pressButton(int n, int a) {
	// n은 버튼 번호, a는 +3 또는 -3으로, 배열에 더할 숫자
	if (a == 0) return;

	for (int i = 0; i < 5; i++) {
		if (button[n][i] == -1)
			break;
		else {
			myClock[button[n][i]] += a;
			// 시계가 범위 외의 숫자를 가리킨다면 주기(12)를 더하거나 빼서 수정
			if (myClock[button[n][i]] % 12 < 3) {
				myClock[button[n][i]] %= 12;
				myClock[button[n][i]] = 12 + myClock[button[n][i]];
			}
			else
				myClock[button[n][i]] %= 12;
		}
	}
}

// 실제 동작을 하는 재귀함수
void run(int n) { 
	/* clock의 모든 원소가 12가 되면 level을 maxLevel과 비교 후 반환
	 * 버튼 번호가 9가 넘어가도 반환
	 */
	bool flag = false;
	for (int i = 0; i < 16; i++)
		if (myClock[i] != 12)
			flag = true;
	if (!flag) {
		if (level < maxLevel)
			maxLevel = level;
		return;
	}
	if (n > 9) return;

	/* 각 버튼당 0번~3번씩 눌러보고, 누른만큼 level에 더해준다.
	 * 다음 버튼을 run 해준다.
	 * 실패했다면 run()이하 코드로 원상복구되며, 다음 회차 시도
	 */
	for (int i = 0; i < 4; i++) {
		pressButton(n, 3*i);
		level += i;
		run(n + 1);
		pressButton(n, -3*i);
		level -= i;
	}
	return;
}

int main() {
	int tc;
	cin >> tc;
	while (tc > 0) {
		for (int i = 0; i < 16; i++)
			cin >> myClock[i];
		level = 0;
		maxLevel = 100;
		run(0);
		// 아무런 값도 찾지 못했다면 -1 반환
		if (maxLevel == 100)
			maxLevel = -1;
		answer.push(maxLevel);
		tc--;
	}
	while (!answer.empty()) {
		cout << answer.front() << endl;
		answer.pop();
	}
	return 0;
}

'버튼을 누르는 순서는 전혀 상관없다'

 

문제를 접하고 무작정 코드를 작성하다 보니 결국 시간은 덧셈의 결과 값이므로 순서가 의미가 없다는 사실을 깨달았다. 따라서 버튼을 0회, 1회, 2회, 3회 눌러보며 각각의 경우 다음버튼을 재귀 호출하여 모든 경우를 탐색했다.

 

​추가적으로 button[]과 같이 문제에서 주어진 변하지 않는 조건은 const로 쓰는 것이 좋다. 또 <ctime.h>에 clock함수가 이미 있으므로, 다른 변수명(myClock)을 사용하지 않으면 채점 시 컴파일 실패가 나오니 참고.

 

ruhz3/CodingTest