ALGOSPOT - Synchronizing Clocks(JAVA)

https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

 

풀이

스위치를 누르는 모든 경우의 수를 탐색(브루트 포스)

 

3, 6, 9, 12를 1, 2, 3, 0으로 변환

for (int j = 0; j < LEN; j++) {
	int temp = Integer.parseInt(st.nextToken());
	watches[j] = (temp / 3) % 4;
}

같은 스위치를 4번 누를 경우 연결된 시계가 다시 원래 시간으로 돌아감 -> 클릭 수 = 0 ~ 3

0 ~ 3번 클릭에 따라 재귀문으로 모든 경우의 수를 확인

private static void calcMin(int switchIdx, int cnt) {
	if (isAllPass()) {
		if (cnt < MIN)
			MIN = cnt;
		return;
	}
	if (switchIdx > 9) return;
 
	for (int i = 0; i < 4; i++) {
		calcMin(switchIdx + 1, cnt + i);
		for (int watchIdx : switchLink[switchIdx]) {
			watches[watchIdx] = (watches[watchIdx] + 1) % 4;
		}
	}
}

 

 

전체 코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int LEN = 16;
    static final int INF = 987654321;
    static int MIN;
    static int[] watches = new int[LEN];
    static int[][] switchLink =
            {
                    {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}
            };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
 
        int testCase = Integer.parseInt(st.nextToken());
 
 
        for (int i = 0; i < testCase; i++) {
            st = new StringTokenizer(br.readLine());
 
            for (int j = 0; j < LEN; j++) {
                int temp = Integer.parseInt(st.nextToken());
                watches[j] = (temp / 3) % 4; // 1,2,3,0 으로 구분
            }
            MIN=INF;
            calcMin(0, 0);
            if (MIN == INF)
                System.out.println(-1);
            else
                System.out.println(MIN);
        }
    }
 
    private static void calcMin(int switchIdx, int cnt) {
 
        if (isAllPass()) {
            if (cnt < MIN)
                MIN = cnt;
            return;
        }
        if (switchIdx > 9) return;
 
        // 0 ~ 3번 클릭
        for (int i = 0; i < 4; i++) {
            calcMin(switchIdx + 1, cnt + i);
            for (int watchIdx : switchLink[switchIdx]) {
                watches[watchIdx] = (watches[watchIdx] + 1) % 4;
            }
        }
    }
    // 모든 시간이 12시(0)인지 확인 
    private static boolean isAllPass() {
        for (int i = 0; i < LEN; i++) {
            if (watches[i] != 0)
                return false;
        }
        return true;
    }
}