[백준 BOJ] 174706 배열 돌리기 4 (python)

문제 링크 : https://www.acmicpc.net/problem/17406

 

이어지는 배열 돌리기 문제입니다.

 

배열을 돌리는 과정은 1, 3과 비슷하지만 배열을 돌릴 부분이 따로 주어지고, 연산을 그저 수행하는 것이 아니라 최적의 연산 순서를 정하기까지 해야합니다.

다만 저는 K가 6이하로 크지 않기때문에 이 순서는 permutation(순열)을 통해 완전탐색을 해주었습니다.

 

배열과 각 순열들 중 하나의 연산들을 get_ans 함수에 입력하여 결과값을 구해주었습니다.

get_lists 함수에 각 과정의 r, c, s, 배열을 입력해주어 돌릴 배열들을 lsts 리스트에 deque로 넣어주었습니다.

deque들을 1씩 rotate해 준 뒤 알맞은 arr에서 알맞은 위치에 재배치 해주었습니다.

이 과정은 배열 돌리기 1, 3 문제의 과정과 똑같습니다.

마지막으로 배열의 최소값이 갱신되면 answer에 저장해주었습니다.

 

import sys
from collections import deque
import itertools
import copy

def get_lists(r, c, s, arr):
    lsts = [deque() for _ in range(s)]
    for i in range(s):
        lsts[i] += arr[r-s+i-1][c-s+i-1:c+s-i-1]
        for j in range(r-s+i-1, r+s-i-1):
            lsts[i].append(arr[j][c+s-i-1])
        lsts[i] += arr[r+s-i-1][c+s-i-1:c-s+i-1:-1]
        for j in range(r+s-i-1, r-s+i-1, -1):
            lsts[i].append(arr[j][c-s+i-1])
    return lsts

def get_ans(arr, rots):
    global answer
    for rot in rots:
        lsts = get_lists(rot[0], rot[1], rot[2], arr)
        for i in range(rot[2]):
            lsts[i].rotate(1)
            j = 0
            chng = [rot[0]-rot[2]+i-1, rot[1]-rot[2]+i-1]
            arr[chng[0]][chng[1]] = lsts[i][j]
            chng[1] += 1
            while chng != [rot[0]-rot[2]+i-1, rot[1]-rot[2]+i-1]:
                j += 1
                arr[chng[0]][chng[1]] = lsts[i][j]
                if chng[1] == rot[1]-rot[2]+i-1:
                    chng[0] -= 1
                elif chng[0] == rot[0]+rot[2]-i-1:
                    chng[1] -= 1
                elif chng[1] == rot[1]+rot[2]-i-1:
                    chng[0] += 1
                elif chng[0] == rot[0]-rot[2]+i-1:
                    chng[1] += 1
                else:
                    print('somthing wrong')
    for line in arr:
        if sum(line) < answer:
            answer = sum(line)

N, M, K = map(int, sys.stdin.readline().rstrip().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, sys.stdin.readline().rstrip().split())))
rots = []
for _ in range(K):
    rots.append(list(map(int, sys.stdin.readline().rstrip().split())))
rots_lst = itertools.permutations(rots, K)
answer = 5000
for rots in rots_lst:
    ans = copy.deepcopy(arr)
    get_ans(ans, rots)
print(answer)