[알고스팟/종만북/완전탐색/재귀] 시계 맞추기(Python)

문제

그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.

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

제목 없음

시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자. 시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할 스위치의 수를 계산하는 프로그램을 작성하시오.

입력

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

출력

각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.

예제 입력

2 12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12 12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6

예제 출력

2 9

출처 : https://www.algospot.com/judge/problem/read/CLOCKSYNC

[접근]

1. 완전탐색 가능? ⇒ 최대 4**10이므로 가능
2. 문제의 특징? 스위치를 4번 누르면 시계가 원복됨 ⇒ 스위치는 0~3번까지 누를 수 있음
3. 풀이기법 : dfs
4. 각 스위치마다 돌아가면서 0~3번 누르고 dfs에 넘겨줌
5. 이 때, 스위치 num += 1 을 해주는 식으로 넘길 것이므로 스위치 num이 최대 num+1이 되었을 때 clock이 모두 12인지 검사하고 answer 업데이트
6. 스위치 누르고 시간을 더하거나 뺄 때, 시계는 12시가 기점인 것을 항상 유념!

[느낀 점]

이 문제는 각 스위치마다 0~3번까지 누를 수 있다는 특징을 잡아내야 풀 수 있는 문제였음

각 문제마다 짧게라도 시뮬레이션 해보면서 특징(제한할 수 있는 조건 등)을 잡아내는 것이 중요!

import sys
sys.setrecursionlimit(10**6)

def is_finished(clocks):
    for clock in clocks:
        if clock != 12:
            return False
    return True

def set_clock(switch, clocks, switch_clocks, time):
    for clock in switch_clocks[switch]:
        clocks[clock] += time
        if clocks[clock] < 0 : clocks[clock] += 12
        if clocks[clock] > 12: clocks[clock] -= 12
        if clocks[clock] == 0: clocks[clock] = 12

answer = int(1e9)

def dfs(switch, clocks, switch_clocks, cnt):
    global answer
    if switch == 10:
        if is_finished(clocks): answer = min(answer, cnt)
        return
    #안 누르고 그냥 넘기기
    dfs(switch+1, clocks, switch_clocks, cnt)
		#1~3번 누른 결과 dfs로 넘기기
    for i in range(1, 4):
        set_clock(switch, clocks, switch_clocks, 3*i)
        dfs(switch+1, clocks, switch_clocks, cnt+i)
        set_clock(switch, clocks, switch_clocks, (-3)*i)
    return

dfs(0, clocks, switch_clocks, 0)
print(answer)

[(참조) 문제 풀 때 입력값]

clocks = [12, 9, 3, 12, 6, 6, 9, 3, 12, 9, 12, 9, 12, 12, 6, 6]
# clocks = [12, 6, 6, 6, 6, 6, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
switch_clocks = [[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]]