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

thinking

파이썬의 슬라이싱 기능을 이용해 한번에 옮기기로 했다.

좌표를 보면 바깥네모에서 안쪽네모로 갈 수록 (노랑->초록) 행과 열에서 s의 크기가 1씩 줄어들기 때문에 s의 range를 1씩 줄이면서 반복문을 돌도록 구성했다.

회전 순서는 1 ≤ K ≤ 6 이므로 최대 6!=720이어서 for문 돌려도 시간복잡도 완전 괜춘하다

회전순서는 파이썬의 itertools 라이브러리를 사용했다

 

 

코드

from itertools import permutations
from copy import deepcopy

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 = 987654321

# 1. 회전 순서 정하기 (최대 6!=720)
for p in permutations(rcs, K):
    # 2. 회전
    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]  # ->
            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]  # <-
            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

    # 3. 각 행의 최소값 찾기
    for row in copy_a:
        ans = min(ans, sum(row))

print(ans)