[BOJ 17406] 배열 돌리기 4 (Java)

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

import java.util.Arrays;
import java.util.Scanner;

public class P17406 {
	static int N, M, K;
	static int[][] A;
	static int[][] temp;
	static Rotate[] rotates;
	static Rotate[] orders;
	static boolean[] check;
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int r,c,s;
		N=sc.nextInt();
		M=sc.nextInt();
		K=sc.nextInt();
		A=new int[N+1][M+1];
		temp=new int[N+1][M+1];
		rotates=new Rotate[K];
		orders=new Rotate[K];
		check=new boolean[K];
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=M; j++) {
				A[i][j]=sc.nextInt();
				temp[i][j]=A[i][j];
			}
		}
		for (int i=0; i<K; i++) {
			r=sc.nextInt();
			c=sc.nextInt();
			s=sc.nextInt();
			rotates[i]=new Rotate(r,c,s);
		}
		perm(0);
		System.out.println(answer);

	}
	
	private static void perm(int cnt) {
		if (cnt==K) {
			for (int i=1; i<=N; i++) {
				for (int j=1; j<=M; j++) {
					A[i][j]=temp[i][j];
				}
			}
			for (int i=0; i<K; i++) {
				clock(orders[i]);
			}
			answer=Math.min(answer, calc());
			return;
		}
		for (int i=0; i<K; i++) {
			if (check[i]) {
				continue;
			}
			check[i]=true;
			orders[cnt]=rotates[i];
			perm(cnt+1);
			check[i]=false;
		}
		
	}

	private static int calc() {
		int[] sums=new int[N+1];
		int min=Integer.MAX_VALUE;
		for (int i=1; i<=N; i++) {
			int tot=0;
			for (int j=1; j<=M; j++) {
				tot+=A[i][j];
			}
			sums[i]=tot;
		}
		for (int i=1; i<=N; i++) {
			min=Math.min(min, sums[i]);
		}
		return min;
	}

	private static void clock(Rotate ro) {
		for (int i=ro.s; i>=0; i--) {
			clock2(ro.r-i, ro.c-i, ro.r+i, ro.c+i);
		}
	}
	
	private static void clock2(int sr, int sc, int er, int ec) {
		int now_r, now_c;
		int temp=A[sr][sc];
		now_r=sr;
		while (now_r<er) {
			A[now_r][sc]=A[now_r+1][sc];
			now_r++;
		}
		now_c=sc;
		while (now_c<ec) {
			A[er][now_c]=A[er][now_c+1];
			now_c++;
		}
		while (now_r>sr) {
			A[now_r][ec]=A[now_r-1][ec];
			now_r--;
		}
		while (now_c>sc) {
			A[sr][now_c]=A[sr][now_c-1];
			now_c--;
		}
		if (!(sr==er && sc==ec)) {
			A[sr][sc+1]=temp;
		}
		
		
	}

	public static class Rotate{
		int r,c,s;
		Rotate(int r, int c, int s) {
			this.r = r;
			this.c = c;
			this.s = s;
		}
	}

}

순열로 가능한 수를 만들어서 배열을 돌려주는 문제이다.

 

배열을 돌려줄 때, s를 기반으로 테두리를 회전하는 방식을 취했다. s가 0이 될때까지 감소시켜주면서, 그에 해당하는 테두리의 값들을 이동시켜준다. 

여기서 주의할점은 (start row , start col) 의 바로 오른쪽 옆 칸에 기존에 저장했던  (start row , start col) 의 값을 넣어줘야 한다는 것이다.

시계 반대방향으로 값을 읽어와서 저장하는 방식을 취하면 된다.