[ 17406 ] [ 구현 ] 배열 돌리기

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

17406번: 배열 돌리기 4

---

풀이 과정

---

1. 함수를 회전시켜주는 함수를 만들어 둔다.
   • r, c, s를 받으면 [r-s, c-s] ~ [r+s, c+s] 정사각형의 테두리를 회전시켜주는 함수
   • 테두리 회전 시, 왼쪽 세로 -> 아래 가로 -> 오른쪽 세로 -> 위쪽 가로 순으로 구현하는게 개인적으로 제일 편했음.
   • 시작점의 값[r-s, c-s]만 따로 저장해둔 다음. 위 순서로 현재 위치 다음칸의 값을 현재 위치의 값으로 덮어씌워준다.
   • 이 때, s를 1 줄여서 재귀함수로 만들어 주면, 내부 사각형도 같이 회전되서 문제에서 제시하는 회전 연산이 된다.
2. permutations 함수를 사용하여서 돌릴수 있는 모든 경우의 수를 구한다.
   • 각각의 케이스를 테스트 해보면서 최솟값 갱신
3. 최솟값을 출력시켜 준다.

---

소스 코드

---

import sys
import copy
from itertools import permutations

input = lambda : sys.stdin.readline().rstrip()
N, M, K = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

def rotate(target, r, c, s):
    if s == 0:
        return
    r, c = r-1, c-1
    start_x, start_y = r-s, c-s
    end_x, end_y = r+s, c+s
    x, y = start_x, start_y
    first_value = target[start_x][start_y]
    
    for i in range(start_x, end_x):
        target[i][start_y] = target[i+1][start_y]

    for i in range(start_y, end_y):
        target[end_x][i] = target[end_x][i+1]

    for i in range(end_x, start_x, -1):
        target[i][end_y] = target[i-1][end_y]

    for i in range(end_y, start_y, -1):
        target[start_x][i] = target[start_x][i-1]
        
    target[start_x][start_y+1] = first_value
    rotate(target, r+1, c+1, s-1)

def get_max_sumation(target):
    return min([sum(q) for q in target])

rotate_information = []
rotate_idx = [i for i in range(K)]
rotate_sequence = list(permutations(rotate_idx, K))

for _ in range(K):
    rotate_information.append(list(map(int, input().split())))

answer = int(10e9)

for sequence in rotate_sequence:
    temp = copy.deepcopy(matrix)

    for i in sequence:
        r, c, s = rotate_information[i]
        rotate(temp, r, c, s)

    answer = min(answer, get_max_sumation(temp))
    
print(answer)