크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.
회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.
다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.
배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.
배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.
설명
앞선 배열 돌리기 1의 심화 문제이다. 배열 돌리기 과정 자체는 거의 똑같으나 추가적인 구현 부분이 있어 코드가 좀 길어진다. 코드가 길어진 만큼 구현 부분에서 함수화를 하지 않으면 코드가 복잡해질 수 있다.
배열을 돌리는 과정 자체는 시작 좌표말고는 배열 돌리기 1 문제와 똑같다. 시작 좌표와 끝 좌표만 잘 지정해주면 배열 돌리기는 배열 돌리기 1보다 쉽다.
연산이 여러 개 주어지는데 연산의 순서에 따라 배열의 값이 달라진다. 구할 수 있는 배열의 값 중 최솟값을 구해야한다. 즉 가능한 모든 연산의 순서를 통해 배열 돌리기를 진행하고 결과로 나온 배열에 대해서 값을 구한다. 모든 연산의 순서를 구하기 위해서 순열을 구현한다. 모든 연산을 하나의 배열에 넣고 index에 대해 순열을 구하여 모든 연산의 순서를 통해 배열 돌리기를 진행했다.
구한 모든 배열의 값 중 최솟값을 출력한다.
코드
//17406번 배열 돌리기4.java
package com.ssafy.webex;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 배열_돌리기_4_17406 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static String line;
static StringTokenizer st;
private static int N;
private static int M;
private static int K;
private static int[][] arr;
private static int[][] arrCopy;
private static int r;
private static int c;
private static int s;
private static int[] dI= {1,0,-1,0};
private static int[] dJ= {0,1,0,-1};
private static int[][] operation;
private static int answer = Integer.MAX_VALUE;
private static boolean[] isSelected;
private static int[] permutation;
public static void move(int r, int c, int s) {
for(int count=0;count<s;count++) {
int i=r-s-1+count;
int j=c-s-1+count;
int start=arr[i][j];
int d=0;
while(d<4) {
int nextI = i+dI[d];
int nextJ = j+dJ[d];
if(r-s-1+count<=nextI && nextI<r+s-count && c-s-1+count<=nextJ && nextJ<c+s-count) {
arr[i][j]=arr[nextI][nextJ];
i = nextI;
j = nextJ;
}
else d++;
}
arr[r-s-1+count][c-s-1+count+1] = start;
}
}
public static int arrValue(int[][] arr) {
int min=Integer.MAX_VALUE;
for(int i=0;i<arr.length;i++) {
int temp=0;
for(int j=0;j<arr[i].length;j++) {
temp+=arr[i][j];
}
if(temp<min)min=temp;
}
return min;
}
public static void permutation(int cnt) {
if(cnt==K) {
for(int i=0;i<N;i++) {
arr[i] = arrCopy[i].clone();
}
for(int i=0;i<K;i++) {
r = operation[permutation[i]][0];
c = operation[permutation[i]][1];
s = operation[permutation[i]][2];
move(r,c,s);
}
int temp = arrValue(arr);
if(answer>temp)answer=temp;
return;
}
for(int i=0;i<K;i++) {
if(isSelected[i]==false) {
isSelected[i]=true;
permutation[cnt]=i;
permutation(cnt+1);
isSelected[i]=false;
permutation[cnt]=0;
}
}
}
public static void main(String[] args) throws IOException {
line = br.readLine();
st = new StringTokenizer(line, " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[N][M];
arrCopy = new int[N][M];
operation = new int[K][3];
isSelected = new boolean[K];
permutation = new int[K];
for(int i=0;i<N;i++) {
line = br.readLine();
st = new StringTokenizer(line, " ");
for(int j=0;j<M;j++) {
arr[i][j]=Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<N;i++) {
arrCopy[i] = arr[i].clone();
}
for(int k=0;k<K;k++) {
line = br.readLine();
st = new StringTokenizer(line, " ");
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
s = Integer.parseInt(st.nextToken());
operation[k][0]=r;
operation[k][1]=c;
operation[k][2]=s;
}
permutation(0);
System.out.println(answer);
}
}
