백준 17406 배열 돌리기 4 (파이썬)

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

17406번: 배열 돌리기 4

1. 입력하는 연산 [r, c, s]를 배열에 저장한다

2. dfs로 순열을 구현하여 연산 순서를 정한다

3. rotate에서 회전을 구현한다. 왼쪽 상단좌표는 lx, ly, 오른쪽 하단좌표는 rx, ry로 저장한다

4. a[lx][ly]값을 before에 저장하고 한 칸씩 이동하면서 현재값을 before로 바꾸고 before을 갱신한다

5. 범위를 벗어날 때마다 방향을 바꿔준다

6. lx, ly 좌표에 위치하게 되면 lx와 ly에 1을 더하고 rx와 ry에 1을 빼서 회전할 범위를 좁혀준다

7. 회전할 수 있을 때 까지 반복한다. lx가 rx보다 크거나 ly가 ry보다 크면 중단한다

8. row의 합 중에서 최소값을 ans에 저장하고 min_ans을 계산한다

9. 순열의 모든 경우를 확인한 후 min_ans를 출력

from collections import deque
from copy import deepcopy
import sys

input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def dfs(cnt):
    global min_ans
    if cnt == k:
        q2 = deepcopy(q)
        min_ans = min(min_ans, rotate(q2))
        return
    for i in range(k):
        if select[i]:
            continue
        select[i] = 1
        q.append(f[i])
        dfs(cnt+1)
        select[i] = 0
        q.pop()


def rotate(q):
    a2 = deepcopy(a)
    while q:
        x, y, z = q.popleft()
        lx, ly, rx, ry = x-z, y-z, x+z, y+z
        while True:
            if lx >= rx or ly >= ry:
                break
            dir = 0
            x, y, before = lx, ly, a2[lx][ly]
            while True:
                nx = x + dx[dir]
                ny = y + dy[dir]
                if not lx <= nx <= rx or not ly <= ny <= ry:
                    dir += 1
                    continue
                temp = a2[nx][ny]
                a2[nx][ny] = before
                before = temp
                x, y = nx, ny
                if [x, y] == [lx, ly]:
                    lx += 1; ly += 1; rx -= 1; ry -= 1
                    break

    ans = sys.maxsize
    for row in a2:
        ans = min(ans, sum(row))
    return ans


n, m, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

f = []
for _ in range(k):
    r, c, s = map(int, input().split())
    f.append([r-1, c-1, s])

select = [0 for _ in range(k)]
q = deque()
min_ans = sys.maxsize
dfs(0)
print(min_ans)