06 - 시계 맞추기 CLOCKSYNC

1. 시계 16개를 모두 12시가 되도록 스위치를 누르는 문제.

 

2,3. 스위치와 시계의 연결은 

const vector linked[10] = { //[switch][clock]형태
{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} };

이렇게 함.

 

스위치를 4번 이상 누르는 경우가 없다.

 

스위치를 누르는 순서는 상관이 없다 (이걸 생각을 못해서 처음에 재귀를 못짬.)

-> 스위치 누르는 순서를 0번-9번으로 강제함.

 

기저:

 누를 스위치가 10번(존재하지않음)일 때 시계들이 정렬돼 있다면 0, 아니면 큰 수 반환

5.

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

const int INF = 9999;

const vector<int> linked[10] = { //[switch][clock]형태
	{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}
};

bool areAligned(int clocks[]) {
	for (int i = 0; i < 16; i++)
		if (clocks[i] != 12) return false;

	return true;
}

int go(int clocks[], int cur) { //cur: 이번에 누를 스위치 번호 누르는 순서는 상관이 없다.->0~9누르는 것으로 순서강제
	if (cur == 10) return areAligned(clocks) ? 0 : INF;

	int ret = INF;
	for (int i = 0; i < 4; i++) { //스위치 0~3번 누르는 경우. 각각의 경우 모두 백트래킹
		for (int j = 0; j < linked[cur].size(); j++) { //스위치 눌렀음. 연결된 시계변환
			clocks[linked[cur][j]] += 3*i;
			if (clocks[linked[cur][j]] > 12) clocks[linked[cur][j]] -= 12;			
		}
        ret = min(i + go(clocks, cur + 1), ret);
		for (int j = 0; j < linked[cur].size(); j++) { //원상복구
			clocks[linked[cur][j]] -= 3*i;
			if (clocks[linked[cur][j]] <= 0) clocks[linked[cur][j]] += 12;			
		}
	}
	return ret;
}

int main() {
	int n;
	cin >> n;
	while (n--) {
		int clocks[16];
		for (int i = 0; i < 16; i++) cin >> clocks[i];
		cout << go(clocks,0);
	}
}

6. 재귀가 도는 부분을 이렇게 바꿔주면 조금 더 빨라진다.

for (int i = 0; i < 4; i++) { //스위치 0~3번 누르는 경우. 각각의 경우 모두 백트래킹
		ret = min(i + go(clocks, cur + 1), ret);
		for (int j = 0; j < linked[cur].size(); j++) { //스위치 눌렀음. 연결된 시계변환
			clocks[linked[cur][j]] += 3;
			if (clocks[linked[cur][j]] > 12) clocks[linked[cur][j]] -= 12;			
		}
	}

 

 

.후기

 책에선 스위치와 시계 연결을 문자열로 표현했다. 이런 방법도 있구나 싶었다. 하지만 익숙한 코드를 쓰라는 원칙엔 조금 어긋나지 않나 싶었다. 100% 내 힘으로 문제를 푸는게 안돼서 불안하다. 하지만 이번문제가 게임판덮기보단 무난했던것 같다.