[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_)
블로그의 정보
개발하는 두부
뚜부니