개발하는 두부

[BOJ] 17406.배열돌리기4

by 뚜부니

 

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

 

이 문제는 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_)
 
블로그의 프로필 사진

블로그의 정보

개발하는 두부

뚜부니

활동하기