[Algorithm] 🕛시계 맞추기

1. 문제 해석

16개의 시계가 존재하고 모두 12시로 맞춰야함

각 시계들은 하나의 버튼에 연결되어 있어서 버튼을 한 번 누르면 3시간 후로 이동함

10번 이내에 시계 맞추기

입력

C(테스트 케이스), 16개 시계의 시간

출력

12시로 맞추기 위해 버튼을 누르는 최소 횟수 (10회 이하)

2. 아이디어

💡 한 개의 스위치는 4번 이상 누르지 않음 (다시 원상태로 복구)
💡 스위치와 연결되어 있는 시계를 배열로 저장해서 이용
💡 재귀함수 사용하여 각각의 스위치를 0-3번까지 눌러보고 가장 작은 값을 결과값에 넣음

3. 풀이

1) 스위치와 연결되어 있는 시계를 배열로 선언

static int linked[][] = {
			{1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
			{0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0},
			{0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1},
			{1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,1,1,1,0,1,0,1,0,0,0},
			{1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1},
			{0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1},
			{0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1},
			{0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0},
			{0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0}
	};

2) 각각의 스위치 0-3번 눌러보고, ret에 작은 값 저장

int ret = INF;
for(int i=0; i<4; i++) {
		ret = Math.min(ret, i+solve(clocks,swtch+1));
		push(clocks,swtch);
}

4. 코드

import java.util.*;

public class ClockSync {
	static int INF = 9999;
	static int SWITCH = 10;
	static int CLOCK = 16;
	static int linked[][] = {
			{1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
			{0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0},
			{0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1},
			{1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,1,1,1,0,1,0,1,0,0,0},
			{1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1},
			{0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1},
			{0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1},
			{0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0},
			{0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0}
	};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int c = sc.nextInt();
		int clocks[] = new int[CLOCK];
		int result[] = new int[c];
		
		for(int i=0; i<c; i++) {
			for(int j=0; j<CLOCK; j++) {
				clocks[j] = sc.nextInt();
			}
			
			result[i] = solve(clocks,0);
			if(result[i] == INF)
				result[i] = -1; 
		}
		
		for(int i=0; i<c; i++)
			System.out.println(result[i]);
	}
	
	public static boolean areAligned(int clocks[]) {
		for(int i=0; i<CLOCK; i++) {
			if(clocks[i] != 12)
				return false;
		}
		
		return true;
	}
	
	public static void push(int clocks[], int swtch) {
		for(int clock=0; clock<CLOCK; clock++) {
			if(linked[swtch][clock] == 1) {
				clocks[clock] += 3;
				if(clocks[clock] == 15)
					clocks[clock] = 3;
			}
		}
	}
	
	public static int solve(int clocks[], int swtch) {
		if(swtch == SWITCH)
			return areAligned(clocks) ? 0:INF;
		
		int ret = INF;
		for(int i=0; i<4; i++) {
			ret = Math.min(ret, i+solve(clocks,swtch+1));
			push(clocks,swtch);
		}
		
		return ret;
	}

}

5. 결과

성공!..