[백준/17406/파이썬] 배열 돌리기 4

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

17406번: 배열 돌리기 4

Problem

• 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
• 배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자.

조건

• 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
• 회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
• 첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.
• 둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.
• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

 

 

SOL

배열을 시계방향으로 돌리는걸 구현하는게 까다로운 문제이다. 

하지만, python에는 강력한 List slicing 기능이 있으므로, Slice를 이용하면 편할거 같다.

그림을 그려보면, 엄청 직관적으로 다가오게 된다.

1. 빨간색을 떼서, 파란색으로 붙인다.

2.왼쪽의 빈칸이 있으니까, 왼쪽 배열을 위로 올려준다.

3. 마찬가지로, 왼쪽 빈칸으로, 아랫줄을 밀어준다.

4. 마찬가지로, 오른쪽 빈칸으로, 오른쪽 줄을 밀어준다.

4단계에서는 뭔가 이상하다. 우리가 원하는건 분명히, 오른쪽 그림과 같은 모양인데, 불 -편하다.

하지만, 이건 변수 2개의 자리만 바꾸면 되는거기 때문에, 상관이 없다! (배열을 떼서 붙이는 과정은 복사하는 과정이므로, 사실 4 4 6 7 8로 구현이 될거라서, 두번째 4를 5로 바꿔주기만 하면된다!)

즉, 저기 파란색 네모 칸의 값을 저장해놨다가, 아랫줄의 값에 대입만해주면 되면 해결되는 간단한 문제이다!

 

#배열 돌려!
from itertools import permutations
from copy import deepcopy

import sys
input= sys.stdin.readline

N,M,K=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N)]
rcs=[list(map(int,input().split())) for _ in range(K)]
ans=sys.maxsize
#회전을 어떻게 구현할건가?

for p in permutations(rcs,K):
    copy_a=deepcopy(A)
    for r,c,s in p:
        r-=1
        c-=1
        for n in range(s,0,-1):
            tmp=copy_a[r-n][c+n]
            # -> 
            copy_a[r-n][c-n+1:c+n+1]=copy_a[r-n][c-n:c+n] 
            # up
            for row in range(r-n,r+n):
                copy_a[row][c-n]=copy_a[row+1][c-n]
            #  <-
            copy_a[r+n][c-n:c+n] = copy_a[r+n][c-n+1:c+n+1]
            # down
            for row in range(r+n,r-n,-1):
                copy_a[row][c+n]=copy_a[row-1][c+n]
            copy_a[r-n+1][c+n]=tmp
    for row in copy_a:
        ans=min(ans,sum(row))

print(ans)