문제 풀이 - 시계 맞추기(JAVA)

시계 맞추기

문제의 분할

이 문제는 그냥 풀려고 하면 꽤 어렵습니다. 하지만 문제의 특성을 이용해 적절히 단순화하면 완전 탐색으로 해결할 수 있습니다.
이 문제에서 처음 깨달아야 할 것은 스위치를 누르는 순서는 중요하지 않다는 것입니다. 스위치를 누르는 순서를 바꿔도 결과는 같습니다.
그래도 어렵습니다. 완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나하나 열거할 수 있어야 하는데, 누르는 횟수는 제한이 없기 때문에 조합의 수는 무한합니다.
시계는 12시간이 지나면 제 자리로 돌아온다는 점을 이용하면 무한한 조합의 수를 유한하게 바꿀 수 있습니다. 어떤 스위치를 네 번 누르면 연결된 시계는 모두 12시간씩 앞으로 이동하기 때문에 하나도 누르지 않은 것과 다름이 없습니다.
현재 시계들의 상태와 이번에 누를 스위치의 번호를 입력하면 이번에 누를 스위치부터 뒤의 스위치를 눌렀을 때 clocks를 12로 맞출 수 있는 최소 횟수를 반환하는 int getMinCount(int[] clocks, int switch) 함수를 만들어야 합니다.

기저 사례의 선택

이번에 누를 스위치의 번호가 마지막 스위치 번호보다 크다면 clocks가 12시에 맞는지 확인하고 맞으면 0, 틀리면 최댓값을 반환합니다.

시간 복잡도 분석

열 개의 스위치 각각 4가지 경우(0번 누르기, 1번 누르기, 2번 누르기, 3번 누르기) 중 선택해야 하므로 전체 경우의 수는 $4^{10}=1,048,576$개 입니다.

구현

import java.util.*;

public class Main {

    // 시계의 상태
    public static int[] clocks = new int[16];
    // 스위치에 연결된 시계를 나타내는 배열
    public static final String[] linked = {"xxx.............", "...x...x.x.x....", "....x.....x...xx", "x...xxxx........",
            "......xxx.x.x...", "x.x...........xx", "...x..........xx", "....xx.x......xx", ".xxxxx..........",
            "...xxx...x...x.."};
    // 답을 저장하는 함수입니다.
    public static int result;

    // 입력값을 받는 함수입니다.
    public static void input(Scanner scanner) {
        for (int i = 0; i < 16; i++) {
            clocks[i] = scanner.nextInt();
        }
    }

    // 문제를 해결하는 함수입니다.
    public static void solve() {
        result = getMinCount(clocks, 0);
        if (result >= 10000000) result = -1;
    }

    // clocks: 현재 시게들의 상태
    // swtch: 이번에 누를 스위치의 번호
    // 가 주어질 때, 남은 스위치들을 눌러서 clocks를 12로 맞출 수 있는 최소 횟수를 반환합니다.
    // 만약 불가능하다면 최댓값을 반환합니다.
    public static int getMinCount(int[] clocks, int swtch) {
        // 기저 사례: 이번에 누를 스위치의 번호가 마지막 스위치의 번호보다 크다면 clocks가 12시가 맞는지 확인 후 맞으면 0, 틀리면 최댓값을 반환합니다.
        if (swtch == 10) return areAligned(clocks) ? 0 : 10000000;
        // 이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도합니다.
        int result = 10000000;
        for (int count = 0; count < 4; count++) {
            result = Math.min(result, count + getMinCount(clocks, swtch + 1));
            push(clocks, swtch);
        }
        // push(clocks, swtch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 됩니다.
        return result;
    }

    // 모든 시계가 12시를 가리키고 있는지 확인합니다.
    public static boolean areAligned(final int[] clocks) {
        for (int i = 0; i < 16; i++) {
            if (clocks[i] != 12) return false;
        }
        return true;
    }

    // 누른 스위치에 연결된 시계들을 3시간 앞으로 이동합니다.
    public static void push(int[] clocks, int swtch) {
        for (int i = 0; i < 16; i++) {
            if (linked[swtch].charAt(i) == 'x') {
                clocks[i] += 3;
                if (clocks[i] == 15) clocks[i] = 3;
            }
        }
    }

    // 답을 출력하는 함수입니다.
    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고