백준-17406-배열돌리기 4

문제

배열 돌리기 4

풀이

1. 문제조건 해석

   배열 회전하는 시뮬레이션 문제이다.

2. 알고리즘

   • 배열을 회전시키는 함수 만든다
     • 바깥쪽에서 안쪽으로 회전 진행한다.
   • 문제의 답은 모든 회전 연산에 대해 가장 최솟값을 구하는 경우
     • 입력 순서대로가 아니다.
     • 회전 순서에 따라 값이 변한다. 따라서 순열 사용함

3. 코드

from copy import deepcopy
from itertools import permutations
from sys import stdin

def rotate(r, c, s, arr):
    for n in range(s, 0, -1):
        tmp  = arr[r-n][c+n]
        arr[r-n][c-n+1:c+n+1] = arr[r-n][c-n:c+n]
        for col in range(r-n, r+n):
            arr[col][c-n] = arr[col+1][c-n]
        arr[r+n][c-n:c+n] = arr[r+n][c-n+1:c+n+1]
        for col in range(r+n, r-n, -1):
            arr[col][c+n] = arr[col-1][c+n]
        arr[r-n+1][c+n] = tmp
    return arr

n, m, k = [int(x) for x in input().rstrip().split()]
origin_arr = []
for _ in range(n):
    origin_arr.append([int(x) for x in input().rstrip().split()])
ops = []
for _ in range(k):
    r, c, s = [int(x) for x in input().rstrip().split()]
    r, c = r-1, c-1
    ops.append((r,c,s))

answer = 100*50*50
results = {}
for op in permutations(ops):
    if op not in results:
        arr = deepcopy(origin_arr)
        
        for r,c,s in op:
            arr = rotate(r, c, s, arr)

        results[op] = min(map(sum, arr))
    
print(min(results.values()))

1. 배운점

   • 문제를 꼼꼼히 이해해야 함. 입력 순서대로 회전 연산이 아니었음.
   • 90도 변환 연산인 줄 알고 뻘짓함. 문제 제대로 이해하기.
   • deepcopy() 연산은 결국 n*n 연산이다.
     • 시간초과 문제가 생겨났음.