[Algospot] CLOCKSYNC (최적화)

#. 문제 

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

* 이 문제의 저작권은 Algospot에 있습니다.

그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.

시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.

시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.

[ 입력 ]

첫 줄에 테스트 케이스의 개수 C (<= 30) 가 주어진다.

각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.

[ 출력 ]

각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.

#. 문제 해결 과정

  1. 문제를 읽고 이해하기

  2. 문제를 익숙한 용어로 재정의 + 추상화

    - 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수 계산

    - 한 스위치를 누를 때마다 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직임

  3. 어떻게 해결할지 계획 세우기(알고리즘, 자료구조 선택) -> 풀이

    - 최적화 문제의 가장 직관적인 방법인 완전 탐색을 사용

  4. 계획 검증하기(수행 시간과 사용 메모리 확인)

    - 수행 시간 : 10초 이내, 사용 메모리 : 64MB 이내

    - 10개의 스위치를 누를 수 있는 최대 수는 0~3회, 4^10=1,048,576

  5. 계획 수행하기

  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아보기

#. 풀이

  1. 스위치와 연결된 시계 정보를 배열에 저장

  2. 테스트 케이스 입력 C(<=30)

  3. 16개 시계의 시간 입력(12, 3, 6, 9) 중 하나

  4. pushSwitch() 함수

    - 스위치를 누르는 순서는 상관 없음. 어떤 스위치를 몇 번 누르냐가 중요 

      -> 0번 스위치부터 9번 스위치까지 0번~3번씩 눌러보면서 모든 경우의 수를 수행

    - 모든 시계는 0~3번 누르는 것이 효율적(4번째는 제자리)

    - 불가능할 경우 -1 출력

#. 코드

import java.io.*;
import java.util.StringTokenizer;
 
public class C68_CLOCKSYNC {
    public static int[] clocksNow;
    public static int C, INF=9999, SWITCH=10, CLOCKS=16;
    /* 스위치와 연결된 시계 정보 */
    public static int[][] linkedClock = {
            {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}
    };
    // 모든 시계가 12시를 가리키는지 확인 
    public static boolean areAligned() {
        for(int ck=0; ck<CLOCKS; ck++) 
            if (clocksNow[ck] % 4 != 0) // 12시를 가리키지 않는 시계가 있을 경우 
                return false;
        return true;
    }
    
    // 스위치를 눌러 시간을 변경해주는 함수 
    public static void push(int swtch) {
        for(int ck=0; ck<linkedClock[swtch].length; ck++) {
            int nClock = linkedClock[swtch][ck];  // 스위치에 연결된 시계 확인
            clocksNow[nClock] += 3;  // 해당 시계를 3시간 추가
            if(clocksNow[nClock] == 15) clocksNow[nClock] = 3;    // 기존 12시였던 시계는 3시로 
        }
    }
    
    public static int readySwitch(int swtch) {
        // 스위치를 다 눌러보았을 경우 결과 반환
        if(swtch == SWITCH) return areAligned() ? 0 : INF;
        // switch를 0번 누르는 경우부터 3번 누르는 경우까지
        int ret = INF;
        for(int cnt=0; cnt<4; cnt++) {
            ret = Math.min(ret, cnt+readySwitch(swtch+1));
            push(swtch);
        }
        return ret;
    }
    
    public static void run() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        /* 테스트 케이스 입력 */
        C = Integer.parseInt(br.readLine().trim());
        assert C <= 30 : "Error :: testCase must be no more than 30.";
        
        while(C-->0) {    // start testCase
            clocksNow = new int[CLOCKS];
            
            /* 16개 시계의 시간 입력 (12, 3, 6, 9 중 하나) */
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            for(int i=0; i<CLOCKS; i++) {
                int tempClock = Integer.parseInt(st.nextToken());
                assert tempClock==12 || tempClock==3 || tempClock==6 || tempClock==9 :
                    "Time can be inputted 3, 6, 9, 12";
                clocksNow[i] = tempClock;
            }
            
            /* 스위치 눌러보기 */
            int result = readySwitch(0);
            bw.write(String.format("%d\n", result>=INF?-1:result));
        }
        bw.close();
    }
    public static void main(String[] args) throws IOException {
        C68_CLOCKSYNC.run();
    }
}
 

#. 결과

  - Input --------------------------------------------------------

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

------------------------------------------------------------------

  - Output --------------------------------------------------------

2

9

------------------------------------------------------------------