[백준] 17406 - 배열 돌리기4 [Python(파이썬)]

문제

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

풀이

완전한 구현 문제다.

순열을 통해 모든 경우의 수를 구한 후, 연산으로 이루어진 순열을 큐에 담아 rotate 함수에 전달한다.

 

회전을 구현하는 과정은 조금 지저분하게 구현했다.

이때 좌측 상단의 좌표를 (ux, uy)로, 우측 하단의 좌표를 (lx, ly)로 두고 좌에서 우로, 상에서 하로 값을 덮어 씌웠다.

이를 위해 모서리의 값을 t1, t2, t3 변수에 담아두었다.

모든 회전이 끝나면(uy < ly and ux < lx) 다음 연산을 수행하게 된다.

 

코드

import sys, itertools, copy

def rotate(pm, arr):
    result = float('inf')
    while pm:
        r, c, s = pm.pop()
        uy, ux, ly, lx = r-s, c-s, r+s, c+s
        while uy < ly and ux < lx:
            t1, t2, t3 = arr[uy][lx], arr[ly][lx], arr[ly][ux]
            for x in range(lx, ux, -1):
                arr[uy][x] = arr[uy][x-1]
            for y in range(ly, uy, -1):
                arr[y][lx] = arr[y-1][lx]
            arr[uy+1][lx] = t1 
            for x in range(ux, lx):
                arr[ly][x] = arr[ly][x+1]
            arr[ly][lx-1] = t2
            for y in range(uy, ly):
                arr[y][ux] = arr[y+1][ux]
            arr[ly-1][ux] = t3
            uy, ux, ly, lx = uy+1, ux+1, ly-1, lx-1
    for i in range(1, n+1):
        raw_sum = sum(arr[i])
        result = min(result, raw_sum)
    return result

arr, ops = [], []
n, m, k = map(int, sys.stdin.readline().split())
org_arr = [[0 for _ in range(m+1)]]+[[0]+[int(x) for x in sys.stdin.readline().split()] for _ in range(n)]
ops = [[int(x) for x in sys.stdin.readline().split()] for _ in range(k)]
min_value = float('inf')

for pm in list(itertools.permutations(ops, k)):
    result = rotate(list(pm), copy.deepcopy(org_arr))
    min_value = min(min_value, result)

print(min_value)