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

NxM 크기 배열 A(각 행에 있는 모든 수의 합 중 최솟값).

ex) 배열A == 4 (1행 합 == 6 / 2행 합 == 4 / 3행 합 == 15)

회전 연산 (r, c, s) -> 가장 왼쪽 윗 칸 == (r-s, c-s) / 가장 오른쪽 아랫 칸 == (r+s, c+s)

시계 방향 회전

(r, c) == r행 c열

ex) 배열A == 6x6 , 회전 연산 == (3, 4, 2)

- 입력

1줄 : 배열 A의 크기 N, M, 회전 연산의 개수 K

2~N줄 : A[i][j]

K줄 : r, c, s

 

- 출력

배열 A의 값의 최솟값

 

 

17406번 배열 돌리기4

방법1) 배열돌리기1과 같이 list를 만든 후에 인덱스로 직접 접근

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

# 회전 조합 생성
for p in permutations(rcs, k):
    temp = deepcopy(a)  # 기존 a 복사
    for r, c, s in p:
        r -= 1
        c -= 1
        for i in range(s, 0, -1):
            tmp = temp[r-i][c+i]
            #위
            temp[r-i][c-i+1:c+i+1] = temp[r-i][c-i:c+] 
            #왼
            for row in range(r-i, r+i): 
                temp[row][c-i] = temp[row+1][c-i]
            #아래
            temp[r+i][c-i:c+i] = temp[r+i][c-i+1:c+i+1] 
            #오
            for row in range(r+i, r-i, -1): 
                temp[row][c+i] = temp[row-1][c+i]
            temp[r-n+1][c+n] = tmp

    # 행 최소값
    for line in temp:
        ans = min(ans, sum(line))

print(ans)

 

 

방법2) dx, dy로 이동

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)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

ans = 999999999

for perm in permutations(rcs,k):
  temp = deepcopy(a)
  for r, c, s in perm:
    for i in range(0, s):
      top = [r-s+i-1, c-s+i-1] #첫 점
      bottom = [r+s-i-1, c+s-i-1] #끝 점
      nx, ny = top #첫 좌표
      tmp = temp[nx][ny] #이동 좌표
      #네 방향 돌기
      for i in range(4):
        while True:
          nx = nx + dx[i]
          ny = ny + dy[i]
          if not (nx >= top[0] and nx <= bottom[0] and ny >= top[1] and ny <= bottom[1]):
            nx = nx - dx[i]
            ny = ny - dy[i]
            break
          tmp, temp[nx][ny] = temp[nx][ny], tmp

  #행 최솟값
  for line in temp:
    ans = min(ans, sum(line))
    
print(ans)

조합을 뽑아서 temp에 임시로 복사해 둠.

rcs 한 세트에서 s개의 고리를 회전 시켜야 함.

첫 점 top은 (r-s, c-s)라고 생각할 수 있으나 인덱스를 고려해서 -1해주고 0부터 s만큼 커질 수 있도록 i를 더해줌.

마지막 점 bottom은 (r+s, c+s)라고 생각할 수 있으나 인덱스를 고려해서 -1해주고 0부터 s만큼 작아지도록 i를 빼줌.

이동 시작 점의 좌표는 nx, ny이고, temp에 본 점을 tmp에 임시로 저장해 둠.

시작점 부터 시계방향으로 4면을 움직이며, top과 bottom을 넘어서지 않는 범위 안에서만 돌아가야 함.

범위를 벗어나게 되면 break하고 초기에 따로 저장해둔 tmp값을 활용.

 

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

17406번: 배열 돌리기 4

방법1 참고 : https://jennnn.tistory.com/74

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

방법2 참고 : https://dev-dain.tistory.com/154

[백준] 17406 : 배열 돌리기 4 (Python3)