[Java/자바 백준 17406] 배열돌리기 4

풀이

연산 수행 순서에 따라 최솟값이 변하므로 순열을 사용했습니다.

순열 뒤, 배열을 돌려줘야하는 배열 돌리기 구현 부분이 조금 헷갈린 문제

 

배열 돌리는 함수는 재귀로 구현했으며, 

시작 x, 시작 y, 끝 x, 끝y 를 구해주고

시작 + 1과 끝 - 1 함수를 돌리면서 둘 값이 같아지면 min값을 구하는 식으로 구현했습니다.

 

또한 배열을 돌릴때, 네 부분으로 나누어서 구현했습니다.

(시작 x, 시작 y)  ~ (시작 x, 끝y) 오른쪽으로 배열 당기기

(시작 x, 끝 y)  ~ (끝 x, 끝y) 아래쪽으로 배열 당기기

(끝 x, 끝 y)  ~ (끝 x, 시작y) 왼쪽으로 배열 당기기

(끝 x, 시작 y)  ~ (시작 x, 시작y) 위쪽으로 배열 당기기

이런 식으로 구현하고

 

각자 모서리 부분은 따로 저장해주었는데

이유는 배열을 당기다보면 모서리 부분이 값이 덮어지는 경우가 발생합니다.

 

예를들어 이런 표가 있어서 

오른쪽으로 당겼다고 가정하면

4값이 사라지게 됩니다. 이 케이스를 처리하기 위해

temp 배열에 위에 표로 예시를 들면 4, 16, 13 값을 담아서 해당 위치가 되면

temp 값에서 꺼내주어서 값을 따로 넣었습니다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int N, M, K, min = Integer.MAX_VALUE;
	static int[][] map;
	static int[][] arr;
	static boolean[] isSelected;
	static int[] numbers;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		arr = new int[K][3];
		isSelected = new boolean[K];
		numbers = new int[K];
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < M ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 0 ; i < K ; i++) {
			st = new StringTokenizer(br.readLine());
			
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			arr[i][2] = Integer.parseInt(st.nextToken());
		}
		
		permutation(0);
		System.out.println(min);
	}
	
	private static void permutation(int cnt) {
		if(cnt == K) {
			int[][] copyMap = new int[N][M];
			for(int i = 0 ; i < N ; i++) {
				copyMap[i] = map[i].clone();
			}
			
			for(int i = 0 ; i < K ; i++) {	
				int lx = arr[numbers[i]][0] - arr[numbers[i]][2] - 1;
				int ly = arr[numbers[i]][1] - arr[numbers[i]][2] - 1;
				int rx = arr[numbers[i]][0] + arr[numbers[i]][2] - 1;
				int ry = arr[numbers[i]][1] + arr[numbers[i]][2] - 1;
				rotate(lx, ly, rx, ry, copyMap);
			}
			
			for(int i = 0 ; i < N ; i++) {
				int answer = 0;
				
				for(int j = 0 ; j < M ; j++) {
					answer += copyMap[i][j];
				}
				
				min = Math.min(min, answer);
			}
			return;
		}
		
		for(int i = 0 ; i < K ; i++) {
			if(isSelected[i]) continue;
			
			isSelected[i] = true;
			numbers[cnt] = i;
			
			permutation(cnt + 1);
			isSelected[i] = false;
			
		}
	}

	private static void rotate(int lx, int ly, int rx, int ry, int[][] copy) {
		//기저조건 
		if(lx == rx && ly == ry) {
			return;
		}
		// 오른 위, 오른 아래, 왼 아래 
		int[] temp = new int[3];
		temp[0] = copy[lx][ry];
		temp[1] = copy[rx][ry];
		temp[2] = copy[rx][ly];
		
		// 오른쪽 회전 
		for(int i = ry ; i  > ly ; i--) {
			copy[lx][i] = copy[lx][i-1];
		}
		
		// 아래 회전 
		for(int i = rx ; i > lx ; i--) {
			if(i == lx + 1) copy[i][ry] = temp[0];
			else copy[i][ry] = copy[i-1][ry];
		}
		
		// 왼 회전 
		for(int i = ly ; i < ry ; i++) {
			if(i == ry - 1) copy[rx][i] = temp[1];
			else copy[rx][i] = copy[rx][i + 1];
		}
		// 위 회전 
		for(int i = lx ; i < rx ; i++) {
			if(i == rx - 1) copy[i][ly] = temp[2];
			else copy[i][ly] = copy[i + 1][ly];
		}
		rotate(lx + 1, ly + 1, rx - 1, ry - 1, copy);
	}
}