[Python] BOJ 17406 - 배열 돌리기 4

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

17406번: 배열 돌리기 4

# 배열돌리기 시리즈 4번째 문제이다.

# 문제에서 요구하는대로 시뮬레이션을 돌려주면 된다.

 

import sys, copy
from itertools import permutations
input = sys.stdin.readline
N, M, K = map(int,input().split())
m = [list(map(int,input().split())) for _ in range(N)]

def rotate(x, y, r, m2):
    # 3. 시계방향 회전연산
    tmp = m2[x][y + r]
    for j in range(y + r, y, -1):
        m2[x][j] = m2[x][j - 1]
    
    tmp2 = m2[x + r][y + r]
    for i in range(x + r, x + 1, -1):
        m2[i][y + r] = m2[i - 1][y + r]
    m2[x + 1][y + r] = tmp

    tmp = m2[x + r][y]
    for j in range(y, y + r - 1):
        m2[x + r][j] = m2[x + r][j + 1]
    m2[x + r][y + r - 1] = tmp2

    for i in range(x, x + r - 1):
        m2[i][y] = m2[i + 1][y]
    m2[x + r - 1][y] = tmp

    return m2

def run(o, m2):
    mn = 5001
    # 2. o에는 회전연산 순서가 저장되어 있다. 예제1: (((3,4,2),(4,2,1)), ((4,2,1),(3,4,2)))
    for oo in o:
        r, c, s = oo[0]-1, oo[1]-1, oo[2]
        while s:
            # 결국 s번을 회전시켜야하므로 while s로 돌려줌
            m2 = rotate(r-s, c-s, s*2, m2)
            s -= 1

    # 순서에 맞게 회전후 최솟값을 check함수로 확인한 뒤 mn에 저장후 return
    mn = min(check(m2), mn)
    return mn

def check(m):
    # 4. 모든 행을 반복문으로 돌며 최솟값 구한 뒤 return
    mn = 5001
    for i in range(N):
        s = 0
        for j in range(M):
            s += m[i][j]
        mn = min(mn, s)
    return mn

# 답의 최댓값은 50x50칸에 모두 100이 있을때이므로 5000이다.
mn = 5001
order = []
for _ in range(K):
    r, c, s = map(int,input().split())
    order.append((r, c, s))

# 1. 모든 순서를 확인해야 하므로 order배열에 K개의 회전연산을 넣고
# permutations으로 모든 경우의 수 p에 저장, run함수를 통해 직접 돌려가며 최솟값 확인
p = list(permutations(order, K))
for o in p:
    m2 = copy.deepcopy(m)
    mn = min(mn, run(o, m2))
print(mn)

(solved.ac 티어: 골드 4)