17406: 배열 돌리기 4

풀이 시간

• 1h 50m
• 처음에 backtracking으로 풀이하려 했으나, 반례가 안잡혀서 permutations를 이용해 모든 연산의 순서를 탐색하여 풀었다

구현 방식

• "배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다." -> permutations을 이용해 brute force

• 배열을 껍질 별로 회전시키는 부분이 구현의 관건이었다 (사실 이 부분은 예전에 "16927: 배열 돌리기 2"(click!)에서 풀어본 적이 있다)
  -> rstart를 r-s로, rend를 r+s로, cstart를 c-s로, cend를 c+s로 정의하여 정사각형의 범위를 정함
  -> 바깥쪽부터 껍질 별로 queue에 시계방향으로 원소들을 넣어주고, queue.rotate(1)을 통해 시계방향으로 1만큼 회전을 시켜준 후, 다시 시계방향으로 queue.popleft()를 해주어 회전연산 수행
  -> slicing 시 인덱스를 설정해주는 부분에서 시간이 꽤 소요되었다

코드

import sys
import copy
from collections import deque
from itertools import permutations


def cal(board, r, c, s):
    rstart = r-s; rend = r+s; cstart = c-s; cend = c+s
    for i in range(s): #껍질별로 수행
        queue = deque([])
        queue.extend(board[rstart+i][cstart+i:cend-i+1])
        queue.extend([row[cend-i] for row in board[rstart+i+1:rend-i]])
        queue.extend(board[rend-i][cstart+i:cend-i+1][::-1])
        queue.extend([row[cstart+i] for row in board[rstart+i+1:rend-i][::-1]])
        queue.rotate(1)
        for j in range(cstart+i, cend-i+1):
            board[rstart+i][j] = queue.popleft()
        for j in range(rstart+i+1, rend-i):
            board[j][cend-i] = queue.popleft()
        for j in range(cend-i, cstart+i-1, -1):
            board[rend-i][j] = queue.popleft()
        for j in range(rend-i-1,rstart+i,-1):
            board[j][cstart+i] = queue.popleft()

            
N, M, K = map(int, sys.stdin.readline()[:-1].split())
origin_board = []
for n in range(N):
    origin_board.append(list(map(int, sys.stdin.readline()[:-1].split())))
cmds = []
for k in range(K):
    r, c, s = list(map(int, sys.stdin.readline()[:-1].split()))
    cmds.append((r-1, c-1, s))

min_result = int(10e9)
for cmd in tuple(permutations(cmds)):
    board = copy.deepcopy(origin_board)
    for r, c, s in cmd:
        cal(board, r, c, s)
    
    local_min_result = int(10e9)
    for i in range(N):
        local_min_result = min(local_min_result, sum(board[i]))
    min_result = min(local_min_result, min_result)
    
print(min_result)

결과