6.8 시계 맞추기 (ID : CLOCKSYNC)

6.8 시계 맞추기 (ID : CLOCKSYNC)

제출일 : 2021-01-09

문제 풀이 시간 : 1H

---

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

문제

)

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

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

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

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

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. # 은 검은 칸, . 는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.

입력

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

출력

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

예제

입력

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

문제 풀이 접근

이 문제를 해결하기 위한 중요 아이디어는 같은 스위치를 4번누를 경우와 0번 누르는 경우가 동일하다는것이다. 다시 말하자면 4번 이상 같은 스위치를 누를 필요가 없다는 것을 의미한다.

따라서 위 문제는 4^10가지의 경우의 수를 탐색하여 문제를 해결 할 수 있기에 모든 경우의 수를 탐색하더라도 제한시간내에 문제를 해결할 수 있다.

따라서 재귀함수를 이용하여 문제를 해결 했다.

코드

언어 : JAVA

실행 시간 : 1340ms

import java.util.Scanner;

public class Main {
    static int INF = Integer.MAX_VALUE >> 1, SWITCH = 10, CLOCK = 16;
    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[] clocks;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int C = sc.nextInt();
        for (int tc = 0; tc < C; tc++) {
            clocks = new int[CLOCK];
            for (int clock = 0; clock < CLOCK; clock++)
                clocks[clock] = (sc.nextInt() / 3) % 4;

            int ret = solve(0);
            System.out.println(ret != INF ? ret : -1);
        }
    }

    private static boolean check() {
        for (int i : clocks)
            if (i != 0)
                return false;
        return true;
    }

    private static void push(int depth) {
        for (int i : switches[depth]) {
            clocks[i]++;
            clocks[i] %= 4;
        }
    }

    private static int solve(int depth) {
        if (depth == SWITCH) {
            return check() ? 0 : INF;
        }

        int ret = INF;
        for (int cnt = 0; cnt < 4; cnt++) {
            ret = Math.min(ret, cnt + solve(depth + 1));
            push(depth);
        }
        return ret;
    }
}