[BOJ][Python3] 5520 - The Clocks

https://www.acmicpc.net/problem/5520

5520번: The Clocks

백준 5520 The Clocks 문제이다.

Figure 1

Figure 1과 같이 3x3 배열로 시계들이 있다.

우리의 목표는 모든 시계를 12시 정각을 가리키도록 최소한의 횟수로 돌리는 것이다.

시계를 돌리는 방법은 Figure2와 같이 9가지가 있다.

각각의 방법을 하나의 Move 라고 칭한다.

시계는 한번 돌릴 때 시계방향으로 90도만큼 돌린다.

 

입력은 한 줄에 공백으로 구분된 3개의 정수씩 총 3줄이 주어진다.

0 = 12시 / 1 = 3시 / 2 = 6시 / 3 = 9시

 

시계를 모두 12시로 돌리는 방법는 매우 많이 존재한다.

최소한의 Move를 사용하여 모든 시계를 12시로 돌리는 방법을

각 Move 번호의 오름차순으로 출력한다.

 

이 문제의 알고리즘 분류는 브루트포스로 되어있지만,

개인적으로는 여기에 백트레킹까지 넣어주는게 더 좋은 분류가 될 수 있다고 생각한다.

 

이 문제를 푸는 아이디어는

"시계는 한번 돌릴 때 시계방향으로 90도만큼 돌린다."

이 곳에 존재한다.

 

이 말인 즉슨 4번 돌리면 360도를 회전하니 처음과 똑같다는 이야기다.

바꿔말하면 1번 Move를 0번쓰나 4번쓰나 8번쓰나 똑같은 결과를 보여준다.

따라서 각각의 Move는 최대 3번까지만 쓸 수 있다.

(그 이상 쓸 바에는 안쓰는게 낫다.)

 

여기에 브루트포스라는 아이디어를 접목하면 다음과 같이 생각할 수 있다.

각각의 Move는 0번, 1번, 2번, 3번 쓸 수 있고,

그런 Move가 총 9개 있다.

계산기를 써보면 4^9 = 262,144 이다.

이 문제의 시간제한은 1초

충분히 모든 경우의 수를 다 돌려볼 수 있다.

 

따라서 중복 순열 나열하는 문제를 풀 듯 재귀를 써서 풀면 된다.

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 2

.

.

.

3 3 3 3 3 3 3 3 3

까지 모두 돌리는 것이다.

 

그리고 저렇게 9개의 숫자를 모두 채웠을 때,

저 숫자를 가지고 시계를 돌렸을 때 0시로 맞춰지는지 체크하면 된다.

 

그런데 재밌는 것은

9개의 시계가 가질 수 있는 상태가 0시 3시 6시 9시로 4가지이다.

이것도 4^9 이다!

Move 가짓수와 똑같다.

그리고 각각의 Move을 그림으로 그려보면 알 수 있 듯

각각의 Move은 절대 서로 겹치는 결과를 낼 수가 없다.

 

그래서 모든 시계가 0이 되는 방법을 하나 찾는 순간 그것이 바로 유일해임을 알 수 있다.

유일해를 찾고나면, 그 유일해를 오름차순으로 정렬해서 출력하면 된다.

 

구현은 다음과 같이 했다.

def back_tracking(depth):
    if depth == 9:
        clocks_copy = [clocks[i].copy() for i in range(3)]
        temp_sum = 0
        for i in range(9):
            if count[i]:
                if i == 0:
                    clocks_copy[0][0] += count[i]
                    clocks_copy[0][0] %= 4
                    clocks_copy[0][1] += count[i]
                    clocks_copy[0][1] %= 4
                    clocks_copy[1][0] += count[i]
                    clocks_copy[1][0] %= 4
                    clocks_copy[1][1] += count[i]
                    clocks_copy[1][1] %= 4
                elif i == 1:
                    clocks_copy[0][0] += count[i]
                    clocks_copy[0][0] %= 4
                    clocks_copy[0][1] += count[i]
                    clocks_copy[0][1] %= 4
                    clocks_copy[0][2] += count[i]
                    clocks_copy[0][2] %= 4
                elif i == 2:
                    clocks_copy[0][1] += count[i]
                    clocks_copy[0][1] %= 4
                    clocks_copy[0][2] += count[i]
                    clocks_copy[0][2] %= 4
                    clocks_copy[1][1] += count[i]
                    clocks_copy[1][1] %= 4
                    clocks_copy[1][2] += count[i]
                    clocks_copy[1][2] %= 4
                elif i == 3:
                    clocks_copy[0][0] += count[i]
                    clocks_copy[0][0] %= 4
                    clocks_copy[1][0] += count[i]
                    clocks_copy[1][0] %= 4
                    clocks_copy[2][0] += count[i]
                    clocks_copy[2][0] %= 4
                elif i == 4:
                    clocks_copy[0][1] += count[i]
                    clocks_copy[0][1] %= 4
                    clocks_copy[1][0] += count[i]
                    clocks_copy[1][0] %= 4
                    clocks_copy[1][1] += count[i]
                    clocks_copy[1][1] %= 4
                    clocks_copy[1][2] += count[i]
                    clocks_copy[1][2] %= 4
                    clocks_copy[2][1] += count[i]
                    clocks_copy[2][1] %= 4
                elif i == 5:
                    clocks_copy[0][2] += count[i]
                    clocks_copy[0][2] %= 4
                    clocks_copy[1][2] += count[i]
                    clocks_copy[1][2] %= 4
                    clocks_copy[2][2] += count[i]
                    clocks_copy[2][2] %= 4
                elif i == 6:
                    clocks_copy[1][0] += count[i]
                    clocks_copy[1][0] %= 4
                    clocks_copy[1][1] += count[i]
                    clocks_copy[1][1] %= 4
                    clocks_copy[2][0] += count[i]
                    clocks_copy[2][0] %= 4
                    clocks_copy[2][1] += count[i]
                    clocks_copy[2][1] %= 4
                elif i == 7:
                    clocks_copy[2][0] += count[i]
                    clocks_copy[2][0] %= 4
                    clocks_copy[2][1] += count[i]
                    clocks_copy[2][1] %= 4
                    clocks_copy[2][2] += count[i]
                    clocks_copy[2][2] %= 4
                elif i == 8:
                    clocks_copy[1][1] += count[i]
                    clocks_copy[1][1] %= 4
                    clocks_copy[1][2] += count[i]
                    clocks_copy[1][2] %= 4
                    clocks_copy[2][1] += count[i]
                    clocks_copy[2][1] %= 4
                    clocks_copy[2][2] += count[i]
                    clocks_copy[2][2] %= 4
                #print(clocks_copy)

        for i in range(3):
            temp_sum += sum(clocks_copy[i])
        if temp_sum == 0:
            #print(count)
            answer.append(tuple(count.copy()))
            find[0] = True
        return

    for i in range(4):
        count[depth] = i
        back_tracking(depth+1)
        if find[0]:
            return

clocks = [list(map(int, input().split())) for _ in range(3)]
count = [0, 0, 0, 0, 0, 0, 0, 0, 0]
find = [False]
answer = []
back_tracking(0)
#print(answer)
for i in range(9):
    for j in range(answer[0][i]):
        print(i+1, end=' ')

코드가 뭔가 길지만ㅋㅋ 사실 시계를 직접 돌려보는 부분의 코드를 직관적으로 노가다 코딩해서 그렇다.

어차피 덧셈의 결과가 그리 크지 않으니 매번 % 연산을 하지 않고 한번에 % 연산을 하도록 하면

더 짧은 코드로 쓸 수 있을 것이다.

 

그리고 주의점.. 1차원 배열의 copy는 문제가 되지 않지만,

2차원 배열을 통채로 copy했더니 앝은복사가 이루어 진 것인지

복사한 배열의 수정이 기존 배열의 수정으로도 이어지는 문제가 있었다.

 

처음에는 이 문제를 몰라서 여러 해가 존재하는 줄 알았다

디버그 모드로 일일히 변수값을 체킹하면서 문제점을 찾고

위와 같이 1차원 배열에 대해서 copy하는 것을 반복하도록 수정했다.