algorithm/baekjoon
[백준] 17406. 배열돌리기4 / python 파이썬
jen jen
2021. 7. 29. 23:42
728x90
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)