배열 돌리기 4 [17406] with 파이썬

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

17406번: 배열 돌리기 4

 

from copy import deepcopy

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

dx, dy = [1,0,-1,0], [0,-1,0,1]
# 큰 값으로 가정
ans = 10000

# 행의 합 중 가장 작은 결과 출력
def value(arr):
    return min([sum(i) for i in arr])

def convert(arr, qry):
    r, c, s = qry
    # 중앙에서 시작해서 오른쪽 대각선 방향부터 시작
    # 배열의 기준 번호가 다르기 때문에 맞춰준다
    r, c = r-1, c-1

    new_arr = deepcopy(arr)
    for i in range(1, s+1):
        rr, cc = r-i, c+i
        # 남 서 북 동 순으로 회전
        for w in range(4):
            for d in range(i*2):
                rrr, ccc = rr+dx[w], cc + dy[w]
                # 회전
                new_arr[rrr][ccc] = arr[rr][cc]
                # 다음값으로 바꿔줌
                rr, cc = rrr, ccc
    return new_arr

def dfs(arr, qry):
    global ans

    # 회전 다 시킨 경우
    # dfs 재귀 종료 시점
    if sum(qry) == k:
        ans = min(ans,value(arr))
        return
   
    for i in range(k):
        if qry[i]:
            continue
        # 백트래킹 - 쿼리 처리했다하고 다시 쿼리 처리 안한 상태로 바꿈
        new_arr = convert(arr, q[i])
        qry[i] = 1
        dfs(new_arr, qry)
        qry[i] = 0

dfs(a, [0 for i in range(k)])
print(ans)