[백준 17406] 배열 돌리기4(Python)

1. 요약

배열돌리기1을 응용한 문제이다. 배열돌리기4의 경우, 시계방향으로 1만큼 회전한다. 그리고 회전 연산이 1개이상 주어지는데, 회전연산의 정의는 아래와 같다.

• 회전 연산은 (r, c, s)로 이루어져 있다.
• (r-s, c-s) ~ (r+s, c+s) 범위내 원소들을 시계 방향으로 1씩 회전한다.

회전 연산을 모두 수행하고나서 각 행에 있는 원소들을 모두 더한다. 그리고 각 행에 대하여 나온 결과 중 가장 작은 값을 배열 값이라고 정의한다. 여기서 우리가 할 일은 회전 연산 순서를 어떻게 정해야 가장 작은 배열 값을 얻을 수 있는지 구하는 문제이다.

2. 아이디어

배열돌리기1의 풀이를 변형한다.(rotate함수 이용)

배열돌리기4의 경우, 초기 배열을 돌릴 지점을 좌측 상단에있는 (y,x)로 잡는다. 초기 높이와 너비의 경우 회전 연산의 정의로 부터 2*s+1 라는 것을 알 수 있다. 좌측 상단에 있는 (y,x)와 높이 너비를 이용해 회전을 하고 이후 (y,x)를 1씩 증가시키고 높이와 너비를 2씩 차감한다. 이를 높이 또는 너비가 0보다 작거나 같을 때까지 시행한다.

한편, 회전 연산의 개수가 많지 않으므로, 완전 탐색을 이용한다. 회전 연산의 순서의 경우를 순열을 이용하여 구한다. 그리고 각 순서에 대해, 회전연산을 하고 배열 값을 구한다. 각 순서에 나온 배열 값 중 가장 작은 값은 선택한다

3. 코드

import sys
from collections import deque
from itertools import permutations

n, m, k = map(int, sys.stdin.readline().rstrip().split())
arr = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(n)]
op_infos = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(k)]
INF = int(1e9)
answer = INF

def rotate(y, x, height, width):
    global copy_arr
    q = deque()

    for i in range(x, x+width):
        q.append(copy_arr[y][i])
    
    for i in range(y+1, y+height):
        q.append(copy_arr[i][x+width-1])
    
    for i in range(x+width-2, x, -1):
        q.append(copy_arr[y+height-1][i])
    
    for i in range(y+height-1, y, -1):
        q.append(copy_arr[i][x])

    q.rotate(1)

    for i in range(x, x+width):
        copy_arr[y][i] = q.popleft()
    
    for i in range(y+1, y+height):
        copy_arr[i][x+width-1] = q.popleft()
    
    for i in range(x+width-2, x, -1):
        copy_arr[y+height-1][i] = q.popleft()
    
    for i in range(y+height-1, y, -1):
        copy_arr[i][x] = q.popleft()

op_orders = tuple(permutations(op_infos))

for order in op_orders:
    copy_arr = [[arr[i][j] for j in range(m)] for i in range(n)]
    for r, c, s in order:
        left_top_y = r - s - 1
        left_top_x = c - s - 1

        height = 2*s + 1
        width = 2*s + 1

        while True:
            if height <= 0 or width <= 0: break
            rotate(left_top_y, left_top_x, height, width)
            height -= 2
            width -= 2
            left_top_y += 1
            left_top_x += 1

    arr_value = INF
    for i in range(n):
        arr_value = min(arr_value, sum(copy_arr[i]))
    answer = min(answer, arr_value)

print(answer)