BOJ. 17406번. 배열 돌리기 4

 

이전과 달라진 점은, 순열에 대한 부분과, 회전를 시키는 위치를 지정하게끔 변경된 것이다. 따라서 순열의 경우의 수를 구하고, 각 경우마다 회전 연산을 수행하여, 각 연산에 따른 결과를 갱신하는 방법으로 문제를 해결했다.

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static ArrayList<Rotate> q = new ArrayList<Rotate>();
	static ArrayList<Rotate> permq = new ArrayList<Rotate>();
	
	static int N,M,K,map[][],tmpMap[][],ans=Integer.MAX_VALUE;
	static int[] dy = {1,0,-1, 0};
	static int[] dx = {0,1, 0,-1};
	static boolean c[];
	
	private static void dataInput() throws NumberFormatException, IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new int[N+1][M+1];
		tmpMap = new int[N+1][M+1];
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0; i<K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());	
			q.add(new Rotate(r,c,s));
		}
		c = new boolean[K];
	}
	
	private static void rotateMap(Rotate cm) {
		int startY = cm.r-cm.s; // 1
		int startX = cm.c-cm.s; // 2
		
		for(int p=0; p<cm.s; p++) {
			int d=0;
			int ox = p+startX, oy=p+startY;
			int tmp = tmpMap[oy][ox];
			
			while(d<4) {
				int ny= oy+dy[d];
				int nx= ox+dx[d];
				if(nx >= startX+p && nx <= startX+p+(2*(cm.s-p))
						&& ny >= startY+p && ny <= startY+p+(2*(cm.s-p)) ) {
					tmpMap[oy][ox] = tmpMap[ny][nx];
					ox = nx;
					oy = ny;
				}else d++;
			}
			tmpMap[p+startY][p+startX+1] = tmp;
		}
	}
	
	private static int calMinRowSum() {
		int res = Integer.MAX_VALUE;
		for(int i=1; i<=N; i++) {
			int tmp=0;
			for(int j=1; j<=M; j++) {
				tmp += tmpMap[i][j];
			}
			res=Math.min(res, tmp);
		}
		return res;
	}
	
	private static void perm(int cnt) {
		if(cnt==K) {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=M; j++) {
					tmpMap[i][j] = map[i][j];
				}
			}
			for(Rotate r : permq) {
				rotateMap(r);
			}
			ans = Math.min(ans, calMinRowSum());
			return;
		}else {
			for(int i=0; i<K; i++) {
				if(!c[i]) {
					c[i] = true;
					permq.add(cnt,q.get(i));
					perm(cnt+1);
					c[i] = false;
					permq.remove(q.get(i));
				}
			}
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		dataInput();
		perm(0);
		System.out.println(ans);
	}

}