시계 맞추기 (골드1)

1. 문제 설명

(1) 시계 맞추기 문제는 아래의 보기들을 이용하여 모든 시계들의 방향을 12시로 돌리는 것이다.

➡	⬆	⬇	⬆
⬆	⬅	➡	⬆
➡	⬆	⬇	➡
⬆	➡	⬆	⬇

( 각 시계들은 3시, 6시, 9시, 12시를 가르키고 있다. )

 

스위치 번호	연결된 시계들
0	0,1,2
1	3,7,9,11
2	4,10,14,15
3	0,4,5,6,7
4	6,7,8,10,12

스위치 번호	연결된 시계들
5	0,2,14,15
6	3,14,15
7	4,5,7,14,15
8	1,2,3,4,5
9	3,4,5,9,13

( 해당 스위치 번호를 누르면 연결된 시계들이 3시간씩 움직이게 된다. )

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫 번째 줄에는 문제 개수 C를 입력한다.

 

(2) 두 번째 줄에는 16(4x4)크기만큼 현재 시계들의 상태를 입력한다.

( 시계의 방향은 0~15범위의 정수를 받으며, ( 3, 6, 9, 12 )의 값으로 초기화 된다. )

 

(3) 이때, 스위치는 이미 정해져 있다고 가정한다.

( 위 그림 참고바람. )

 

출력 조건

(1) 시계들을 모두 12시 방향으로 돌리기 위해 스위치를 누르는 최소 횟수를 출력한다.

 

입력 예제

2
12 6 6 6
6 6 12 12
12 12 12 12
12 12 12 12
12 9 3 12
6 6 9 3
12 9 12 9
12 12 6 6

출력 예제

2
9

 

3. 코드

: 이 문제는 이미 시계 개수와 스위치가 이미 정해져 있다고 가정한다.

public class CLOCKSYNC {
    // 각각 시계, 개수
    static int[] clocks  = new int[16];
    static int clocks_size = clocks.length;
    
    // 각각 스위치, 개수
    static int[][] switches = {
            {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 }        
    };
    static int switches_size = switches.length;
    
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        int C = Integer.parseInt(sc.readLine());
        for(int i=0; i<C; i++) {
            // 현재 시계의 상태를 초기화하는 과정
            for(int y=0; y<4; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0+(y*4); x<4*(y+1); x++) {
                    clocks[x] = (Integer.parseInt(st.nextToken())/3)%4;
                }
            }
            sb.append(solve(0)+"\n");
        }
        System.out.println(sb);
    }
    
    // 재귀 호출하는 메인 메서드
    static int solve(int cnt) {
        // cnt가 스위치 개수만큼 온다면 바로 check() 수행
        if(cnt==switches_size) return check()? 0:9999;
        
        // 비교할 수 없을 만큼 
        // ret 값을 초기화
        int ret=9999;
        
        // 4번 이상 돌리면 다시 원위치로 시계가 돌아온다는
        // 아이디어를 가지고 4까지만 수행
        // ex) i가 0, 1, 2 --> 회전 | 4 --> 다음 경우의 수를 위해 다시 원위치
        for(int i=0; i<4; i++) {
            ret = Math.min(ret, i+solve(cnt+1));
            rotate(cnt);
        }
        return ret;
    }
    
    // 현재 시계 상태가 12시를 가르키고 있다면
    // true 리턴하는 메서드
    static boolean check() {
        for(int i:clocks) {
            if(i!=0) {
                return false;
            }
        }
        return true;
    }
    
    // 시계를 회전하는 메서드
    static void rotate(int cnt) {
        for(int i:switches[cnt]) {
            clocks[i] = (clocks[i]+1)%4;
        }
    }
}