고고학 최고의 발견

from copy import deepcopy from math import inf from itertools import product def turn(board, r, c, n): for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1), (0, 0)]: if 0 <= r+dr < len(board) and 0 <= c+dc < len(board[0]): board[r+dr][c+dc] = (board[r+dr][c+dc] + n) % 4 def finished(board): for x in board[-1]: if x != 0: return False return True def solution(clockHands): board = clockHands length = len(board) answer = inf for ns in product([0, 1, 2, 3], repeat=length): cnt = 0 newboard = deepcopy(board) # 첫 줄을 돌려봅니다. for c, n in zip(range(length), ns): turn(newboard, 0, c, n) cnt += n # 첫 줄을 모두 0으로 만들기 위해서 둘째 줄을 돌리고, # 둘째 줄을 모두 0으로 만들기 위해서 셋째 줄을 돌리고, # length-1번째 줄을 모두 0으로 만들기 위해서 length번째 줄을 돌립니다. for r in range(1, length): for c in range(length): if (x := newboard[r-1][c]) != 0: turn(newboard, r, c, (4 - x) % 4) cnt += (4 - x) % 4 # 전부 0이 되었으면, 최솟값을 업데이트합니다. if finished(newboard): answer = min(answer, cnt) return answer