[BOJ] 17406.배열돌리기4

 

17406번: 배열 돌리기 4

 

이 문제는 NxM 크기의 배열 A가 주어지며, 배열 A의 값은 각 행의 합 중 최솟값을 나타냅니다.

배열 회전 연산은 (r, c, s)로 이루어져있는데, r행 c열을 둘러싼 정사각형을 시계방향으로 돌립니다.

여기서 정사각형은 가장 왼쪽 윗칸이 r-s행, c-s열, 가장 오른쪽 아랫칸이 r+s행, c+s행인 정사각형입니다.

만약, s가 2일 경우

가장 왼족 윗칸이 r-s+1행, c-s+1열, 가장 오른쪽 아랫칸이 r+s-1행, c+s-1행인 정사각형에 대해서도 수행해야 합니다.

 

회전 연산 순서에 따라 최솟값이 달라지므로 연산 순서에 대한 순열을 만들어서 회전 연산을 실행합니다.

또한, r, c는 1부터 시작이므로 실제 연산 시에는 r-1, c-1에 대해 수행해야 합니다.

각각의 순열에 대해 회전 연산 수행 후 배열 A의 최솟값을 출력합니다.

 

# 배열돌리기4
import sys
input = sys.stdin.readline

def rotation(matrix, r, c, s) : # 회전 연산 함수
    for i in range(s) :
        r1, c1, r2, c2 = r-s+i, c-s+i, r+s-i, c+s-i # 가장 왼쪽 윗칸 r,c 가장 오른쪽 아랫칸 r,c 저장
        temp = matrix[r1][c1] # 가장 왼쪽 윗칸 저장
        # c1열
        for idx in range(r1, r2) :
            matrix[idx][c1] = matrix[idx+1][c1]
        # r2행
        for idx in range(c1, c2) :
            matrix[r2][idx] = matrix[r2][idx+1]
        # c2열
        for idx in range(r2,r1,-1) :
            matrix[idx][c2] = matrix[idx-1][c2]
        # r1행
        for idx in range(c2, c1+1, -1) :
            matrix[r1][idx] = matrix[r1][idx-1]
        matrix[r1][c1+1] = temp # 저장한 가장 왼족 윗칸 값을 바로 다음 열에 넣어줌
        
    return matrix
    
    

def dfs(L, cur) : # 순열을 만들어 회전 연산 실행 후 최솟값을 찾는 함수
    global min_
    if L == K :
        opelist = [operation[idx] for idx in visitied]
        copy_matrix = [m[:] for m in matrix]
        for r, c, s in opelist :
            copy_matrix = rotation(copy_matrix, r-1, c-1, s)
        min_ = min(min_, min([sum(temp) for temp in copy_matrix]))
        return
    for i in range(K):
        if visitied[i] == -1 : # 아직 값을 채우지 않았다면
            visitied[i] = cur # 현재 추가해야 할 인덱스 값 대입
            dfs(L + 1, cur + 1)
            visitied[i] = -1

if __name__=="__main__" :
    N, M, K = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    operation = [list(map(int, input().split())) for _ in range(K)]

    min_ = 2147000000 # 배열 A의 값을 큰 수로 초기화
    visitied = [-1] * K # 순열 생성을 위한 리스트
    dfs(0, 0)
    print(min_)