[ALGOSPOT]CLOCKSYNC

풀이

• 각 스위치를 0번부터 3번까지 누르는 경우에 대해 완전탐색
• 반복문으로 스위치를 i번 누른후(i>=0 && i<3) 다음 스위치에 대해 재귀를 호출하고, 하나의 경우가 탐색이 끝나면 원래의 상태로 되돌린다.

python 코드 ( 시간초과 )

import sys

switchs = [
    [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]
]

testcase = int(sys.stdin.readline())
for t in range(testcase):
    clocks = list(map(int,sys.stdin.readline().split()))

    for i in range(16):
        clocks[i]=int((12-clocks[i])/3)
    
    def press_switch(n,m):
        for i in range(len(switchs[n])):
            clocks[switchs[n][i]]=(clocks[switchs[n][i]]-m+4)%4

    def restore(n,m):
        for i in range(len(switchs[n])):
            clocks[switchs[n][i]]=(clocks[switchs[n][i]]+m+4)%4

    def comb(index,ans,check):
        if sum(clocks)==0:
            #print(check)
            return ans
        
        if index>=10:
            return 100
        
        tmp = 100
        for i in range(4):
            press_switch(index,i)
            tmp = min(tmp,comb(index+1,ans+i,check))
            restore(index,i)

        return tmp
        
    answer = comb(0,0,[])
    if answer>30:
        print(-1)
    else:
        print(answer)

java 코드 (통과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {

    static public int[][] switchs = {
        {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 public List<Integer> clocks = new ArrayList<>();

    static public void main(String[] args) throws IOException {
        int testcase;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        testcase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testcase; i++) {
            clocks = Arrays.asList(br.readLine().split(" ")).stream()
                .map(s -> (12 - Integer.parseInt(s)) / 3)
                .collect(Collectors.toList());
            /*System.out.println(clocks);*/
            clocksync(clocks);
        }
    }

    static public void pressSwitch(int n, int m) {
        for (int i = 0; i < switchs[n].length; i++) {
            clocks.set(switchs[n][i], (clocks.get(switchs[n][i]) - m + 4) % 4);
        }
    }

    static public void restore(int n, int m) {
        for (int i = 0; i < switchs[n].length; i++) {
            clocks.set(switchs[n][i], (clocks.get(switchs[n][i]) + m + 4) % 4);
        }
    }

    static public int combination(int index, int ans) {
        if (clocks.stream().mapToInt(Integer::intValue).sum() == 0) {
            return ans;
        }
        if (index >= 10) {
            return 100;
        }

        int tmp = 100;
        for (int i = 0; i < 4; i++) {
            pressSwitch(index, i);
            tmp = Math.min(tmp, combination(index + 1, ans + i));
            restore(index, i);
        }

        return tmp;
    }

    static public void clocksync(List<Integer> clocks) {
        int answer = combination(0, 0);
        if (answer > 30) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }
}

• 두개가 같은 로직인데도 python의 경우는 통과되지 못했다.