[python] algospot ClockSync 문제풀이

문제

4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다.

이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.

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

시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.

-> 문제 링크 : https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

 

문제 풀이

이 문제를 아무 제약조건 없이 현재 시계를 12시로만 맞추는 함수를 만들어서 재귀를 돌리게 되면 모든 시계를 12시로 맞추는 방법의 수는 무한대가 되게 된다. 스위치 하나를 몇번이든 누를 수가 있기 때문이다.

 

하지만 스위치는 4번을 누르면 제자리로 돌아오게 된다. 즉, 같은 스위치를 4번 이상 누를 필요가 없다는 뜻이다.

이 정보를 이용하면 각 스위치를 누르는 최대 횟수를 4번으로 제한할 수 있다.

 

스위치 번호가 주어지고 스위치를 누르는 문제가 들어오면 스위치를 0번, 1번, 2번, 3번 누르는 경우 4가지가 존재한다.

즉, 현재 문제가 4개의 부분문제로 쪼개진다. 그러므로 문제의 시간복잡도는 O(4^n)이다. 

문제에서 n은 최대 10이니까 4^10으로 완전 탐색으로 구현해도 제한 시간 안에 문제를 해결할 수 있다.

 

문제를 풀기 위해 push_switch, syncClock 함수를 구현했다.

* push_switch(num, time) : num번째 스위치를 time번 누르는 효과를 낸다.

* syncClock(now) : 재귀가 도는 부분이다. now는 현재 눌러야 할 스위치 번호를 나타내고 함수 내에서 반복문과 재귀를 통해 스윛를 0번, 1번, 2번, 3번 누르는 부분 문제로 분할해서 풀어나간다.

 

코드

# 종만북

import sys

sys.setrecursionlimit(10**6)

# 1개
N = int(sys.stdin.readline().rstrip())

switch = [
    [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 push_switch(num, time) :

    for _ in range(time) :
        for i in switch[num] :
            clocks[i] = ( clocks[i] + 1 ) % 4

def syncClock(now) :

    if any(clocks) == False :
        return 0

    if now == 10 :
        return float('inf')

    ret = float('inf')

    for i in range(0,4) :
        ret = min(ret, i + syncClock(now+1))
        push_switch(now, 1)
    # for문 한바퀴 다 돌면 다시 clocks 상태가 원상복구되니까 clocks를 다시 되돌릴 필요는 없는 듯


    return ret

for _ in range(N) :

    clocks = list(map(int,sys.stdin.readline().rstrip().split()))
    clocks = [ i//3 % 4 for i in clocks ]

    dp = [None for _ in range(len(clocks))]

    ans = syncClock(0)

    if ans == float('inf') :
        print('-1')
    else :
        print(ans)

 

초기 접근 방식과 오답의 원인

그러나 내가 짠 파이선 코드로는 시간 초과가 나온다. 

파이선 자체의 속도 문제인지 코드 문제인지 모르겠다. 추후에 이유와 개선 방법을 찾아야겠다.

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.