[백준] 배열 돌리기 4.py

import sys
from itertools import permutations
from collections import deque
from copy import deepcopy
import math
y, x, n = map(int, sys.stdin.readline().split())
original_maps = [list(map(int, sys.stdin.readline().split())) for _ in range(y)]
arrs = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

# 1. 모든 경우의 수
candidates = permutations(arrs, len(arrs))

# 배열 A의 값 구하는 함수
def get_A(maps):
    return min([sum(maps[y]) for y in range(len(maps))])

# 회전시킬 부분의 index를 deque로 구하는 함수.
def get_square(maps, r, c, s):
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = deque()
    # 회전할 구간의 단면 길이
    length = s * 2 + 1
    
    start = (r - s, c - s)
    count = 1
    idx = 0
    dy, dx = dirs[idx]
    while True:
        y, x = start
        queue.append(start)
        ny, nx = y + dy, x + dx
        count += 1
        start = ny, nx
        if count == length:
            count = 1
            idx += 1
            # 전부 다 회전했으면 break
            if idx == len(dirs):
                break    
            dy, dx = dirs[idx]
    return queue
        
maps = deepcopy(original_maps)     
mins = math.inf      
for each_case in candidates:
    maps = deepcopy(original_maps)
    for order in each_case:
        r, c, s = order
        r -= 1
        c -= 1
        for i in range(1, s+1):
            coords = get_square(maps, r, c, i)
            # 해당 좌표에서 얻은 값
            values = deque([maps[y][x] for y, x in coords])
            # 값 회전
            values.rotate(1)
            # 좌표에 회전한 값 배치
            for (y,x), value in zip(coords, values):
                maps[y][x] = value
    mins = min(mins, get_A(maps))
    
print(mins)