알고스팟 : 시계 맞추기 (완전 탐색, 최적의 해)

 

완전탐색으로 시계를 모두 12시로 맞추는 모든 경우의 수를 구하고 그 중 스위치를 누른 최소의 갯수를 구하려고 했으나 시간초과가 발생하였다. 

 

import math 
inf = math.inf
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]
]

def is_aligned_clock(clock) :
    for time in clock : 
        if time != 12 :
            return False
    return True

def push_switch(clock, switch_num):
    for i in range(len(switches[switch_num])) :
        clock[switches[switch_num][i]] += 3
        if clock[switches[switch_num][i]] == 15 : 
           clock[switches[switch_num][i]] = 3

def match_clock (clock, switch_num) :
    if switch_num == 10 :
        if is_aligned_clock(clock):
            return 0
        else : 
            return inf
    result = inf
    
    if len(switches[switch_num]) ==1 : 
        cnt =  4 - ((clock[switches[switch_num]]//3)% 4)
        return min(result, cnt + match_clock(clock, switch_num + 1))

    for i in range(4) :
        result = min(result, i + match_clock(clock, switch_num+1))
        push_switch(clock, switch_num)
    return result


c = int(input())
for _ in range(c):
    clock = list(map(int, input().split()))
    answer = match_clock(clock, 0)
    if answer == inf:
        print(-1)
    else :
        print(answer)

 

 

 

시간초과 생각을 해보니 이 문제에서는 스위치에 따라 영향을 받는 시계가 주어졌는데 여기서 단일 시계를 조작하는 스위치, 즉 하나의 스위치만 조작할 수 있는 시계를 보니 1, 4, 9번 스위치에 8, 11, 12, 13번 시계가 존재 했다. 여기서 8번 시계와 12번 시계는 스위치 4번만 조작할 수 있으므로 시작단계에서 8, 12번 시계의 값이 동일하지 않다면 모든 시계를 12시로 맞출 수 없다. 

 

재귀를 시작하기 전에 각각의 유일 시계를 조작하여 12시로 맞춘 값을 계산하고 단일 스위치 번호가 넘어올 때는 다음 스위치를 조작하도록 변경한 다음 정답이 존재할때 이전에 계산한 값을 더해줌으로서 시간초과를 해결할 수 있었다. 

 

이 문제는 완전 탐색으로 계산하려고 하니 다음과 같이 불필요한 경우를 제외시켜줌으로서 해결할 수 있었는데, 다른 방법으로 더욱 효율을 높여 계산할 수 있을 것 같아 추가적인 공부가 필요하다! 

inf = float('inf')
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]
]

# 하나의 시계가 조작될 수 있는 스위치 
unique_clock_switch = [1, 4, 9]
# 조작하는 스위치가 하나인 단일 시계 
unique_clock = [11, 12, 13]

# 시계가 정렬되어 있는지 확인 
def is_aligned_clock(clock) :
    for time in clock : 
        if time != 12 :
            return False
    return True

# 스위치를 눌러 스위치가 조작하는 모든 시계를 회전 
def push_switch(clock, switch_num):
    for i in range(len(switches[switch_num])) :
        clock[switches[switch_num][i]] += 3
        if clock[switches[switch_num][i]] == 15 : 
           clock[switches[switch_num][i]] = 3

# 시계를 정렬할 수 있는 경우의 수 계산 (스위치 번호를 높여주면서 깊이를 증가한다)
def match_clock (clock, switch_num) :
	# 스위치 끝까지 오면 결과 리턴 
    if switch_num == 10 :
        if is_aligned_clock(clock):
            return 0
        else : 
            return inf
    # 단일 조작 스위치는 이전에 계산해서 더 진행하면 시계를 흐트린다. 다음 단계로 넘겨준다.     
    if switch_num in [1, 4, 9] :
        return match_clock(clock, switch_num+1)
        
    result = inf	
    # 현재 버튼을 누른 횟수 + 시계 모양에서 12시로 모든 시계를 맞추는데 버튼을 누른 횟수 (모든 경우 조회)
    for i in range(4) :
        result = min(result, i + match_clock(clock, switch_num+1))
        push_switch(clock, switch_num)
    return result

c = int(input())
for _ in range(c):
    clock = list(map(int, input().split()))
    
    # 8번 시계와 12번 시계가 동일해야 모든 시계를 12시로 맞출 수 있다. 
    if clock[8] != clock[12]:
        print(-1)
        continue
    prior_cnt = 0
    
    # 단일 조작 버튼은 미리 눌러서 시계를 맞추고 시작 
    for i in range(len(unique_clock)):
        cnt = (4-clock[unique_clock[i]]//3)% 4
        prior_cnt+=cnt
        for j in range(cnt):
            push_switch(clock, unique_clock_switch[i])
    
    answer = match_clock(clock, 0)+ prior_cnt
    if answer == inf:
        print(-1)
    else :
        print(answer)