[JAVA] [BOJ] 17406. 배열돌리기 4

문제를 요약을 하면

1. 배열이 입력으로 들어온다.

2. 회전하는 명령어가 입력으로 들어온다.

3. 회전하는 명령어를 순서를 바꾸면서 실행하여 최소값을 찾는다.

 

참고로 저는 제 코드를 참고하시지 않는 것을 추천드립니다.... 정말 힘들게 짰어요

 

 회전하는 명령어의 경우 중심점의 좌표와 좌표로부터의 거리? 좌표부터의 가로 혹은 세로 길이를 나타내고

무조건 시계방향으로 돌리면 된다.

 

 나의 경우.... 정말 힘들게 생각했는데

문제를 풀 당시 시계방향으로 돌면서 모든 것을 돌리는 방법을 찾지 못했고 따라서

한줄씩 하면 어떨까라는 생각으로 풀었다.

 

코드를 보면 ( 이해하기 힘들지만....)  중심점을 기준으로 위의 가로줄, 밑의 가로줄, 오른쪽의 세로줄, 왼쪽의 세로줄을 하였고

 

이 경우 명령어가 (3,4,2) 일때 예로들어 (1,6) (2,5) (4,3) (5,2)의 좌표가 Temp로 저장되어 사용된다.

 

3,4,2 일때를 예로 들어 자세히 말하면

1. (1,6)의 좌표를 저장후 한칸씩 오른쪽으로 옮긴다.

2. (2,5)의 좌표를 저장후 한칸씩 오른쪽으로 옮긴다.

3. (4,3)의 좌표를 저장후 한칸씩 왼쪽으로 옮긴다.

4. (5,2)의 좌표를 저장후 한칸씩 왼쪽으로 옮긴다.

 

5. (5,6)부터 위로 올라가며 아래로 한칸씩 당긴후 (2,6)에는 (1,6)의 좌표를 넣어준다.

6. (4,5)부터 위로 올라가며 아래로 한칸씩 당긴후 (3,5)에는 (2,5)의 좌표를 넣어준다.

7. (2,3)부터 아래로 내려가며 위로 한칸씩 당긴후 (3,3)에는 (4,3)의 좌표를 넣어준다.

8. (1,2)부터 아래로 내려가며 위로 한칸씩 당긴후 (4,2)에는 (5,2)의 좌표를 넣어준다.

 

인데 Temp 배열의 경우 배열의 길이는 s * 2로 해주면 된다.

 

코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	static int arrMin;
	static int[] order;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		arrMin = Integer.MAX_VALUE;
		String[] input = br.readLine().split(" ");
		int n= Integer.parseInt(input[0]);
		int m = Integer.parseInt(input[1]);
		int k = Integer.parseInt(input[2]);
		int[][] arr = new int[n][m];
		int sum = 0;
		for(int i=0; i<n; ++i) {
			input = br.readLine().split(" ");
			sum = 0;
			for(int j=0; j<m; ++j) {
				arr[i][j] = Integer.parseInt(input[j]);
				sum += arr[i][j];
			}
			arrMin = sum;
		}
		int[][] command = new int[k][3];
		order = new int[k];
		for(int i=0; i<k; ++i) {
			input = br.readLine().split(" ");
			for(int j=0; j<3; ++j) {
				command[i][j] = Integer.parseInt(input[j]);
			}
		}
		selectOrder(k, 0, new boolean[k], arr, command);
		bw.write(""+arrMin+"\n");
		bw.close();
		br.close();
	}
	
	
	static void selectOrder(int k, int depth, boolean[] select, int[][] arr, int[][] command) {
		if(depth == k) {
			conduct(arr, command);
			return;
		}
		for(int i=0; i<k; ++i) {
			if(select[i]) continue;
			select[i] = true;
			order[depth] = i;
			selectOrder(k, depth+1, select, arr, command);
			select[i] = false;
		}
	}

	static void conduct(int[][] arr, int[][] command) {
		int[][] temp = new int[arr.length][arr[0].length];
		for(int i=0; i<arr.length; ++i) {
			for(int j=0; j<arr[i].length; ++j) {
				temp[i][j] = arr[i][j];
			}
		}
		// 원본은 보존해야하니 복사본 만듬
		
		for(int i=0; i<order.length; ++i) {
			temp = turnArr(command[order[i]], temp);
		}
		
		int min = Integer.MAX_VALUE;
		int sum = 0;
		for(int i=0; i<temp.length; ++i) {
			sum = 0;
			for(int j=0; j<temp[i].length; ++j) {
				sum+= temp[i][j];
			}
			if(sum < min) {
				min = sum;
			}
		}
		if(min < arrMin) {
			arrMin = min;
		}
		
		
	}
	
	static int[][] turnArr(int[] command, int[][] arr){
		int r = command[0]-1;
		int c = command[1]-1;
		int s = command[2];
		int rowStart = r-s;
		int rowEnd = r+s;
		int colStart = c-s;
		int colEnd = c+s;
		int rightIdx = 0;
		int leftIdx = 0;
		int upIdx = 0;
		int downIdx = 0;
		int[] rowTemp = new int[s*2];
		for(int i=rowStart; i<r; ++i) {
			rowTemp[rightIdx] = arr[i][colEnd-rightIdx];
			for(int j=colEnd-rightIdx; j>colStart+rightIdx; --j) {
				arr[i][j] = arr[i][j-1];
			}
			++rightIdx;
		}
		for(int i=r+1; i<=rowEnd; ++i) {
			rowTemp[s+leftIdx] = arr[i][colStart + s - leftIdx - 1];
			for(int j=colStart + s - leftIdx - 1; j<colEnd - s + leftIdx + 1; ++j) {
				arr[i][j] = arr[i][j+1];
			}
			++leftIdx;
		}
		for(int j=colEnd; j>c; --j) {
			for(int i=rowEnd-downIdx; i>rowStart+downIdx; --i) {
				arr[i][j] = arr[i-1][j];
			}
			arr[rowStart+downIdx+1][j] = rowTemp[downIdx];
			++downIdx;
		}
		
		for(int j=c-1; j>=colStart; --j) {
			for(int i = rowStart + s - upIdx - 1; i< rowEnd - s + upIdx + 1; ++i) {
				arr[i][j] = arr[i+1][j];
			}
			arr[rowEnd - s + upIdx][j] = rowTemp[upIdx + s];
			++upIdx;
		}
		
		
//		for(int i=0; i<arr.length; ++i) {
//			for(int j=0; j<arr[i].length; ++j) {
//				System.out.print(arr[i][j]+"\t");
//			}
//			System.out.println();
//		}
//		System.out.println();
		
		return arr;
	}

}