[Algorithm] ๐ŸŒช๏ธ๋ฐฑ์ค€ 17144 ๋ฐฐ์—ด ๋Œ๋ฆฌ๊ธฐ4

0. ๋ฌธ์ œ

ํฌ๊ธฐ๊ฐ€ Nร—M ํฌ๊ธฐ์ธ ๋ฐฐ์—ด A๊ฐ€ ์žˆ์„๋•Œ, ๋ฐฐ์—ด A์˜ ๊ฐ’์€ ๊ฐ ํ–‰์— ์žˆ๋Š” ๋ชจ๋“  ์ˆ˜์˜ ํ•ฉ ์ค‘ ์ตœ์†Ÿ๊ฐ’์„ ์˜๋ฏธํ•œ๋‹ค. ๋ฐฐ์—ด A๊ฐ€ ์•„๋ž˜์™€ ๊ฐ™์€ ๊ฒฝ์šฐ 1ํ–‰์˜ ํ•ฉ์€ 6, 2ํ–‰์˜ ํ•ฉ์€ 4, 3ํ–‰์˜ ํ•ฉ์€ 15์ด๋‹ค. ๋”ฐ๋ผ์„œ, ๋ฐฐ์—ด A์˜ ๊ฐ’์€ 4์ด๋‹ค.

1 2 3
2 1 1
4 5 6
๋ฐฐ์—ด์€ ํšŒ์ „ ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค. ํšŒ์ „ ์—ฐ์‚ฐ์€ ์„ธ ์ •์ˆ˜ (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 (4, 2, 1) ์—ฐ์‚ฐ ์ˆ˜ํ–‰ ํ›„ (3, 4, 2) ์—ฐ์‚ฐ ์ˆ˜ํ–‰ ํ›„
๋ฐฐ์—ด A์— (3, 4, 2), (4, 2, 1) ์ˆœ์„œ๋กœ ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜๋ฉด ๋ฐฐ์—ด A์˜ ๊ฐ’์€ 12, (4, 2, 1), (3, 4, 2) ์ˆœ์„œ๋กœ ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜๋ฉด 15 ์ด๋‹ค.
๋ฐฐ์—ด A์™€ ์‚ฌ์šฉ ๊ฐ€๋Šฅํ•œ ํšŒ์ „ ์—ฐ์‚ฐ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋ฐฐ์—ด A์˜ ๊ฐ’์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด๋ณด์ž. ํšŒ์ „ ์—ฐ์‚ฐ์€ ๋ชจ๋‘ ํ•œ ๋ฒˆ์”ฉ ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋ฉฐ, ์ˆœ์„œ๋Š” ์ž„์˜๋กœ ์ •ํ•ด๋„ ๋œ๋‹ค.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— ๋ฐฐ์—ด A์˜ ํฌ๊ธฐ N, M, ํšŒ์ „ ์—ฐ์‚ฐ์˜ ๊ฐœ์ˆ˜ K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๋ฐฐ์—ด A์— ๋“ค์–ด์žˆ๋Š” ์ˆ˜ A[i][j]๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ๋‹ค์Œ K๊ฐœ์˜ ์ค„์— ํšŒ์ „ ์—ฐ์‚ฐ์˜ ์ •๋ณด r, c, s๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ
๋ฐฐ์—ด A์˜ ๊ฐ’์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก rotate ์ˆœ์„œ๋ฅผ ์ •ํ•˜๋Š” ์ˆœ์—ดํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ฆ
๐Ÿ’ก ๊ฐ€์žฅ ์ž‘์€ ์—ด์˜ ํ•ฉ์„ ์ฐพ๊ธฐ ์œ„ํ•ด ๋ฐฐ์—ด์„ ๋Œ๋ฆด ๋ฒ”์œ„๋ฅผ ์ฐพ์Œ
๐Ÿ’ก ๋ฐฐ์—ด ๋Œ๋ฆฌ๊ธฐ
๐Ÿ’ก ๋Œ๋ฆฐ ํ›„, ๋ฐฐ์—ด์˜ ํ•ฉ ๊ณ„์‚ฐํ•จ

2. ํ•ต์‹ฌ ํ’€์ด

  1. rotate ์ˆœ์„œ๋ฅผ ์ •ํ•˜๋Š” ์ˆœ์—ดํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ฆ
static void dfs(int cnt) {
	if(cnt == k) {
		int[][] copy = new int[n][m];
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				copy[i][j] = map[i][j];
			}
		}
		findMin(copy);
		return;
	} 
		
	for(int i=0; i<k; i++) {
		if(!visited[i]) {
			visited[i] = true;
			result[cnt] = i;
			dfs(cnt+1);
			visited[i] = false;
		}
	}
}
  1. ๊ฐ€์žฅ ์ž‘์€ ์—ด์˜ ํ•ฉ์„ ์ฐพ๊ธฐ ์œ„ํ•ด ๋ฐฐ์—ด์„ ๋Œ๋ฆด ๋ฒ”์œ„๋ฅผ ์ฐพ์Œ
static void findMin(int[][] copy) {
	for(int i=0; i<result.length; i++) {
		int idx = result[i];
		int lx = op[idx][0] - op[idx][2] - 1;
		int ly = op[idx][1] - op[idx][2] - 1;
		int rx = op[idx][0] + op[idx][2] - 1;
		int ry = op[idx][1] + op[idx][2] - 1;
		rotate(lx, ly, rx, ry, copy);
	}
	cal(copy);
}
  1. ๋ฐฐ์—ด ๋Œ๋ฆฌ๊ธฐ
static void rotate(int lx, int ly, int rx, int ry, int[][] copy) {
	if(lx == rx && ly == ry)
		return;
		
	int[] tmp = new int[3];
	tmp[0] = copy[lx][ry];
	tmp[1] = copy[rx][ry];
	tmp[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] = tmp[0];
        else copy[i][ry] = copy[i - 1][ry];
    }
		
    for(int i = ly; i < ry; i++) {
       	if(i == ry - 1) copy[rx][i] = tmp[1];
        else copy[rx][i] = copy[rx][i + 1];
    }
        
    for(int i = lx; i < rx; i++) {
        if(i == rx - 1) copy[i][ly] = tmp[2];
        else copy[i][ly] = copy[i + 1][ly];
    }   
        
   	rotate(lx + 1, ly + 1, rx - 1, ry - 1, copy);
 }
  1. ๋Œ๋ฆฐ ํ›„, ๋ฐฐ์—ด์˜ ํ•ฉ ๊ณ„์‚ฐํ•จ
static void cal(int[][] copy) {
	for(int i=0; i<copy.length; i++) {
		int sum = 0;
		for(int j=0; j<copy[i].length; j++) {
			sum += copy[i][j];
		}
		min = Math.min(sum, min);
	}
}

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Imple_14 {
	static int[][] map;
	static int[][] op;
	static int n, m, k;
	static int min = Integer.MAX_VALUE;
	static boolean[] visited;
	static int[] result;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		n = Integer.parseInt(s[0]);
		m = Integer.parseInt(s[1]);
		k = Integer.parseInt(s[2]);
		map = new int[n+1][m+1];
		
		op = new int[k][3];
		
		for(int i=0; i<n; i++) {
			s = br.readLine().split(" ");
			for(int j=0; j<m; j++) {
				map[i][j] = Integer.parseInt(s[j]);
			}
		}
		
		for(int i=0; i<k; i++) {
			s = br.readLine().split(" ");
			for(int j=0; j<3; j++) {
				op[i][j] = Integer.parseInt(s[j]);
			}
		}
		
		visited = new boolean[k];
		result = new int[k];
		dfs(0);
		
		System.out.println(min);
	}
	
	static void dfs(int cnt) {
		if(cnt == k) {
			int[][] copy = new int[n][m];
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					copy[i][j] = map[i][j];
				}
			}
			findMin(copy);
			return;
		} 
		
		for(int i=0; i<k; i++) {
			if(!visited[i]) {
				visited[i] = true;
				result[cnt] = i;
				dfs(cnt+1);
				visited[i] = false;
			}
		}
	}
	
	static void findMin(int[][] copy) {
		for(int i=0; i<result.length; i++) {
			int idx = result[i];
			int lx = op[idx][0] - op[idx][2] - 1;
			int ly = op[idx][1] - op[idx][2] - 1;
			int rx = op[idx][0] + op[idx][2] - 1;
			int ry = op[idx][1] + op[idx][2] - 1;
			rotate(lx, ly, rx, ry, copy);
		}
		cal(copy);
	}
	
	static void cal(int[][] copy) {
		for(int i=0; i<copy.length; i++) {
			int sum = 0;
			for(int j=0; j<copy[i].length; j++) {
				sum += copy[i][j];
			}
			min = Math.min(sum, min);
		}
	}
	
	static void rotate(int lx, int ly, int rx, int ry, int[][] copy) {
		if(lx == rx && ly == ry)
			return;
		
		int[] tmp = new int[3];
		tmp[0] = copy[lx][ry];
		tmp[1] = copy[rx][ry];
		tmp[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] = tmp[0];
            else copy[i][ry] = copy[i - 1][ry];
        }
		
        for(int i = ly; i < ry; i++) {
            if(i == ry - 1) copy[rx][i] = tmp[1];
            else copy[rx][i] = copy[rx][i + 1];
        }
        
        for(int i = lx; i < rx; i++) {
            if(i == rx - 1) copy[i][ly] = tmp[2];
            else copy[i][ly] = copy[i + 1][ly];
        }   
        
        rotate(lx + 1, ly + 1, rx - 1, ry - 1, copy);
	}
}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ