[python] 알고리즘 문제 해결 전략 1권 :: 시계 맞추기 (p168) 문제

6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

문제

4x4 격자 형태로 배치된 열여섯 개의 시계가 있습니다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있는데, 이 시계들이 모두 12시를 가리키도록 바꾸고 싶습니다. 시계의 시간을 조작하는 유일한 방법은 열 개의 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 세 개에서 많게는 다섯 개의 시계에 연결되어 있습니다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직입니다. (12시일때는 3시로, 3시=>6시, 6시 =>9시, 9시=>12시)

스위치들과 그들이 연결된 시계들의 목록이 주어지고 현재 가리키는 시간들이 주어졌을 때 모든 시계를 12시로 돌리기 위해 최소한 스위치를 몇 번이나 눌러야 하는지 계산하는 프로그램을 작성하세요.

시간 및 메모리 제한

프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.

입력

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

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 시계들을 모두 12시로 돌려놓기 위해 스위치를 눌러야 할 최소 횟수여야 하며, 만약 이것이 불가능할 경우 -1을 출력해야 합니다.

스위치 번호	연결된 시계들	스위치 번호	연결된 시계들
0	0,1,2	5	0,2,14,15
1	3,7,9,11	6	3,14,15
2	4,10,14,15	7	4,5,7,14,15
3	0,4,5,6,7	8	1,2,3,4,5
4	6,7,8,10,12	9	3,4,5,9,13

나의 답

import sys

c = int(input()) # testcase

switch_list=[[0,1,2],[0,2,14,15],[0,4,5,6,7],[1,2,3,4,5],[3,4,5,9,13],[3,7,9,11],[3,14,15],[4,5,7,14,15],[4,10,14,15],[6,7,8,10,12]]

def click_switch(index,time_list,type):
    tmp_list = switch_list[index]

    for i in tmp_list:
        time_list[i]+=3*type
        if time_list[i]>12:
            time_list[i] -=12
        if time_list[i]<0:
            time_list[i]+=12
    return time_list

def SwitchNum(time_list,sum_click,min_click):

    clock_index= int(-1)
    for clock in time_list: # 12시가 아닌 첫 시계 찾기
        if clock!=12:
            clock_index = time_list.index(clock)
            break

    if clock_index == -1: # 모두 12시라면
        return sum_click
    if sum_click > min_click: # 지금까지 나온 최소 횟수를 초과했으면
        return min_click

    tmp_switches = list()
    save_switches = list()
    for index in range(0,len(switch_list)):
        if clock_index in switch_list[index]:
            tmp = switch_list[index].index(clock_index)
            store_index = len(tmp_switches)
            for i in range(0,len(tmp_switches)):
                if tmp<tmp_switches[i][1]:
                    store_index = i
            tmp_switches.insert(store_index,[index,tmp])

    for i in tmp_switches:
        save_switches.append(i[0])

    for index in save_switches:
        time_list = click_switch(index,time_list,1)
        sum_click+=1
        net = SwitchNum(time_list,sum_click,min_click)
        time_list = click_switch(index,time_list,-1)
        sum_click-=1
        if net<min_click:
            min_click = net

    return min_click

for case in range(0,c):
    clock_time = list()
    try:
        clock_time=input().split()
    except:
        print("clock time input error")
        #sys.exit()
    for i in range(0,16):
        clock_time[i] = int(clock_time[i])

    click_num = int(0)
    result = list()
    result.append(SwitchNum(clock_time,click_num,987654321))

for i in result:
    print(i)

설명

처음에 하나의 조각을 스위치 하나 누르기라고 보고 함수를 구현했다. 책에서 주어진 스위치의 순서를 그대로 하여 12시가 아닌 첫번째 시계를 찾아, 해당 시계를 포함하고 있는 스위치를 배열에 담은 후 배열에서 하나씩 꺼내면서 재귀적으로 처리하려고 하였다.

이와 같은 방법으로 구현을 했을 때 첫번째 예제부터 무한 재귀함수에 들어가서 오버플로우 에러가 났다. 따라서 주어진 스위치 순서대로 고려하는 것이 아니라, 스위치를 고려하는 순서를 바꿔보자는 생각에 스위치를 index 순서대로 배열에 넣어보았다. 여기서 index 순이란 12시가 아닌 첫번째 수가 해당 배열에 들어있는 위치이다.

ex_) 12 6 6 6 6 .... 에서 12시가 아닌 첫번째 수는 2번째 시계에 있는 6시이다. 2번째 시계(index:1)와 연결된 스위치는 0,8이 있는데 0에서의 1의 index는 1이고 8에서의 1의 index는 0이므로 8번째 버튼을 더 우선적으로 눌러본다.

이렇게 구현한 이유는 12 6 6 6 6 ... 이라는 예제에서 오버플로우가 뜬 이유가 8번 스위치보다 0번 스위치를 우선하였기 때문에 0번 스위치를 고려하는 과정에서 무한 재귀에 빠져서 라고 생각했기 때문이다.

이렇게까지 구현했으나 첫번째 문제는 해결하였지만, 두번째 문제는 역시 오버플로우때문에 해결하지 못하였다. 그래서 중간에

if sum_click > min_click: # 지금까지 나온 최소 횟수를 초과했으면
        return min_click

라는 코드를 추가하여 이때까지 12시를 맞출 수 있는 최소의 스위치 수를 찾았다면, 그 스위치 수보다 넘어가는 경우는 고려하지 않기로 하였다. 하지만 이 때도 처음과 마찬가지로 잘못된 길에 들어서면 무한 재귀를 발생시킬 수 있으므로 모든 상황에 있어서 해결방안은 아니었다.

또 다시 생각해본 방안은 계속해서 12시가 아닌 첫번째 시계를 찾기보다는 1번째 시계부터 16번째 시계까지 차례대로 진행하면서 12시가 아닌 시계를 바꾸는 방안이다. 하지만 이와 같은 방안이 시간, 공간적인 문제를 줄여줄 것이라고 생각지 않는다..

메모리

Partition of a set of 140558 objects. Total size = 10299088 bytes.
Index Count % Size % Cumulative % Kind (class / dict of class)
0 45997 33 3304117 32 3304117 32 str
1 34805 25 1467044 14 4771161 46 tuple
2 17279 12 1025087 10 5796248 56 bytes
3 8666 6 730012 7 6526260 63 types.CodeType
4 1395 1 670536 7 7196796 70 type
5 8043 6 579096 6 7775892 76 function
6 2115 2 505916 5 8281808 80 dict (no owner)
7 1395 1 405012 4 8686820 84 dict of type
8 361 0 291340 3 8978160 87 dict of module
9 367 0 150860 1 9129020 89 set
<381 more rows. Type e.g. '_.more' to view.>

첫번째 예제 구현 메모리이다.

항상 비슷하다.

주어진 답과 다른 점

1. 스위치를 누르는 순서는 중요하지 않다.

   계산해야 할 것은 스위치를 몇 번 누르는 것이냐 인데, 나는 오버플로우를 피하기 위해 순서에 너무 집착했던 것 같다.

2. 무한한 경우의 수를 유한하게 만들자.

   시계가 12시간이 지나면 돌아온다는 점을 이용해서 어떤 스위치건 최대 3번 이상 누르지 않게 하자.

   정말 생각지도 못했던 가정

   전체 경우의 수가 4(0~3번)의 10승밖에 안됨

3. return 방식

   계속 헷갈리는 것 중에 하나인데, 주어진 답에서는 10번째 스위치에 닿을 때를 기점으로 하여 정렬이 되었으면 0을 return하게 해서 solve 함수의 return을 타고 ret을 차례로 거쳐 마지막에 ret으로 return 되게 하였다. 이러한 방식은 결국 애초에 4가지 경우의 수를 완전 탐색한다는 아이디어가 있어야 하고, 있었어도 구현을 생각하긴 어려웠던 것 같다. (잘 익혀두자!)

마지막 경우의 수 따질 때 return 값을 이용해 return 값을 거슬러 올라올 수 있게 만들기