6.8_시계 맞추기_CLOCKSYNC

문제 설명

algospot.com :: CLOCKSYNC

• 4 x 4로 배치된 16개의 시계가 있다.
• 각 시계는 12시, 3시, 6시, 9시를 가리킨다.
• 시계와 연결된 스위치 10개가 있다.
• 각 스위치는 3개 ~ 5개의 시계와 연결되어 있고 그 정보는 주어진다.
• 스위치를 한 번 누르면, 연결된 시계의 시간에 + 3시간이 된다.

=> 모든 시계를 12시로 돌리기 위해 스위치를 눌러야 하는 최소한의 횟수를 출력하기

 

 

문제 풀이

• 스위치는 무한하게 누를 수 있을까?
  12시인 시계와 연결된 스위치를 누를 때마다,
  시간은 12시(0번 누르기) -> 3시(1번) -> 6시(2번) -> 9시(3번) -> 12시(4번) 으로
  원래 상태로 돌아온다.
  즉, 스위치를 4번 이상 누를 필요가 없다.
  
  
• 어떤 스위치를 먼저 눌러야 할까?
  예를 들어, 12시를 가리키는 1번 시계와 연결된 A스위치와 B스위치가 있다고 하자.
  A -> B 순서로 스위치를 누르면 시계는 6시를 가리키고,
  B -> A 순서로 스위치를 누르면 시계는 6시를 가리킨다.
  즉, 스위치를 누르는 순서는 신경쓰지 않아도 된다.

따라서 이 문제는 

0번 스위치 0회 ~ 3회 -> 1번 스위치 0회 ~ 3회 -> 2번 스위치 0회 ~ 3회 -> ...

처럼 각 스위치를 0회 ~ 3회 눌러보면서 모든 시계가 12시가 되는 최소 횟수를 구하면 풀리는 조합 문제이다.

 

문제 풀이 코드

#include <iostream>
#define MAXPUSHCNT 31	// 각 스위치를 3번씩 누른다면 최대 30번

using namespace std;

//{시계 개수, 시계 index1, 시계 index2, ... }
int switches[10][6] = {{3,0,1,2}, {4,3,7,9,11}, {4,4,10,14,15}, {5,0,4,5,6,7}, {5,6,7,8,10,12}, {4,0,2,14,15}, {3,3,14,15}, {5,4,5,7,14,15}, {5,1,2,3,4,5}, {5,3,4,5,9,13}};
int clockArr[16];
int minValue;

bool isAllTwelve() {
	bool allTwelve = true;
	for (int i = 0; i < 16; ++i) {
		if (clockArr[i] != 12) {
			allTwelve = false;
			break;
		}
	}
	return allTwelve;
}

// 한 버튼을 4번 이상 누르면 같은 상태가 된다.
// 즉, 0~9번 버튼을 0,1,2,3번 누르는 경우를 따라가보자.
void pushSwitch(int index, int cnt) {
	if (cnt >= minValue) return;	// 최소값보다 커지면 더 이상의 연산 필요 없음

	if (isAllTwelve()) {			// 모든 시계 12시 확인
		minValue = cnt;
		return;
	}

	if (index == 10) return;		// 스위치는 10개까지

	for (int pushCnt = 0; pushCnt < 4; ++pushCnt) {
		pushSwitch(index + 1, cnt + pushCnt);			// 0번째는 안누르는 경우
		for (int i = 0; i < switches[index][0]; ++i) {	// 해당 스위치에 연결된 시계 돌리기
			clockArr[switches[index][i+1]] += 3;
			if (clockArr[switches[index][i+1]] > 12) clockArr[switches[index][i+1]] %= 12;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(0);

	int C;
	cin >> C;

	for (int tc = 0; tc < C; ++tc) {
		minValue = MAXPUSHCNT;
		for (int i = 0; i < 16; ++i) {
			cin >> clockArr[i];
		}
		pushSwitch(0, 0);
		cout <<  (minValue == MAXPUSHCNT ? -1 : minValue) << endl;
	}

	return 0;
}