[백준] 17406 배열 돌리기 4 python 풀이

문제

• 난이도: 골드4
• 알고리즘 분류: 구현, 브루트포스, 백트래킹
• 요약: 주어진 배열에 여러 회전 연산을 각각 한 번씩 적용하며, 이 연산들의 순서를 자유롭게 변경하여 회전한 후 얻을 수 있는 모든 배열 중 최솟값을 찾아 출력하기

 

풀이

순열

backtracking을 이용해서 순열을 구현할 수 있지만, itertools 모듈의 permutations 함수를 통해 더 빠르게 구할 수 있다.

permutations(객체 n, 뽑을 개수 r)
객체: [[a,b,c], [d,e,f]]
반환값: ([a,b,c], [d,e,f]), ([d,e,f], [a,b,c])
	  경우의 수에 대한 쌍을 튜플 형식으로 리턴

하나의 회전 순열이 다른 순열에 영향이 가지 않도록 deepcopy를 통해 복사를 진행해야한다.

 

회전

회전 연산에 대해 r, c, s가 주어지는데 이 값을 보면 (r, c)를 기준으로 상하좌우로 s만큼 떨어진 좌표들이 값이 시계방향으로 회전하는 것을 볼 수 있다.

 

(r, c)를 중심으로 s만큼 떨어진 각 커브에서 각각 y, x 좌표의 범위를 구할 수 있다.
r-s+i-1 (top_r) <= y <= r+s-i-1 (bottom_r)
c-s+i-1 (top_c) <= x <= c+s-i-1 (bottom_c)

이 범위 내에서 시계방향으로 값을 회전시키기 위해 네 변을 순서대로 swap을 통해 처리한다.

 

구현 과정
1. 가장 바깥쪽 커브부터 내부로 진행하며 각 커브를 처리한다.
2. 커브에 대해 시계방향으로 네 변의 값을 변경한다.
3. 하나의 회전 순열이 완료되면, 결과로 얻은 배열 최솟값을 계산하고 비교하여 업데이트한다.

 

코드

from itertools import permutations
from copy import deepcopy
import sys

input = sys.stdin.readline

n, m, k = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

rotate = [] # 회전 연산 (r, c, s)
for _ in range(k):
    rotate.append(list(map(int, input().split())))

#     동  남  서  북
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

min_row = int(1e9)

# permutation(n, r): 서로 다른 n개 중 r개를 골라 순서 나열
for p in permutations(rotate, k):
    cp_arr = deepcopy(arr)

    for r, c, s in p:
        # 바깥 커브부터 회전
        for i in range(s):
            top_r, top_c = r-s+i-1, c-s+i-1 # 배열 좌표는 0부터 시작이므로 -1
            bottom_r, bottom_c = r+s-i-1, c+s-i-1

            y, x = top_r, top_c
            prev = cp_arr[y][x]

            for dir in range(4): # 네 변 확인
                while True:
                    ny = y + dy[dir]
                    nx = x + dx[dir]

                    if not(top_r <= ny <= bottom_r and top_c <= nx <= bottom_c):
                        break

                    cp_arr[ny][nx], prev = prev, cp_arr[ny][nx]
                    y, x = ny, nx

    # 모든 회전 연산 수행 후 최솟값 업데이트
    for row in cp_arr:
        min_row = min(min_row, sum(row))

print(min_row)