Baekjoon 17406 배열 돌리기 4 JAVA

17406번: 배열 돌리기 4

문제

크기가 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[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

1 2 3 2 5 6 3 8 7 2 1 3 8 2 3 1 4 5 3 4 5 1 1 1 9 3 2 1 4 3	1 8 2 3 2 5 3 2 3 7 2 6 8 4 5 1 1 3 3 3 1 1 4 5 9 2 1 4 3 1	1 8 2 3 2 5 3 2 3 7 2 6 3 8 4 1 1 3 9 3 5 1 4 5 2 1 1 4 3 1
배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후
1 2 3 2 5 6 3 8 7 2 1 3 8 2 3 1 4 5 3 4 5 1 1 1 9 3 2 1 4 3	1 2 3 2 5 6 3 8 7 2 1 3 3 8 2 1 4 5 9 4 3 1 1 1 3 2 5 1 4 3	1 8 2 3 2 5 3 8 2 7 2 6 3 4 3 1 1 3 9 2 1 1 4 5 3 5 1 4 3 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의 값의 최솟값을 출력한다.

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

풀이

Rotate함수는 좌측, 하단, 우측, 상단의 칸수를 한칸씩 옮기는 함수이다. 

S 변수를 이용하여 r,c 기준점으로부터 S칸만큼 떨어진 상태에서 한칸씩 줄여나가며 시계방향으로 회전시킨다.

 

permutation 함수는 들어온 r, c, s로 만들수 있는 모든 수열을 만들어서 모든 경우의 수를 탐색하는 순열생성 알고리즘이다.

 

func는 마지막에 실제로 r, c, s를 이용한 회전을 직접시키는 부분이다.

앞서 만든 순열함수를 이용하여 모든 경우의 수를 탐색한다. 이때 들어온 맵은 계속 변화하기에 brr이라는 임시테이블을 만들어서 임시테이블을 이용하여 각 회전의 결과를 생성하고, 그 과정이 끝날때마다. 한줄씩 모든 값을 더해서 가장 작게 더해지는 열을 답으로 리턴한다. 

참고

2022.02.09 - [Algorithm/Baekjoon] - Baekjoon 16926 배열 돌리기 1 JAVA

2022.02.09 - [Algorithm/Baekjoon] - Baekjoon 16927 배열 돌리기 2 JAVA

2022.02.09 - [Algorithm/Baekjoon] - Baekjoon 16935 배열 돌리기 3 JAVA

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr, locations, permutation;
	static int n, m, k, cnt;
	static boolean[] isChecked;
	static StringBuilder sb;
	static int[] res = new int[10];
	
    public static void rotate(int[][] brr, int r, int c, int s) {
		while (s > 0) {
			int save = brr[r - s][c - s];
			for (int i = r - s; i < r + s; i++) // left side
				brr[i][c - s] = brr[i + 1][c - s];
			for (int j = c - s; j < c + s; j++) // bottom side
				brr[r + s][j] = brr[r + s][j + 1];
			for (int i = r + s - 1; i >= r - s; i--) // right side
				brr[i + 1][c + s] = brr[i][c + s];
			for (int j = c + s - 1; j >= c - s; j--) // top side
				brr[r - s][j + 1] = brr[r - s][j];

			brr[r - s][c + 1 - s] = save;
			s--;
		}
	}
	
	public static void permutation(int depth) {
		if (depth == k) {
			for(int i=0;i<k;i++)
				permutation[cnt][i]=res[i];
			cnt++;
			return;
		}
		for (int i = 0; i < k; i++) {
			if (!isChecked[i]) {
				isChecked[i] = true;
				res[depth]=i;
				permutation(depth + 1);
				isChecked[i] = false;
			}
		}
	}

	public static int func() {
		int min=Integer.MAX_VALUE;
		int[][] brr = new int[n + 2][m + 2];

		for (int rot = 0; rot < permutation.length; rot++) {
			for (int i = 1; i <= n; i++) // Array Initialization
				for (int j = 1; j <= m; j++)
					brr[i][j] = arr[i][j];

			for (int l = 0; l < permutation[rot].length; l++)
				rotate(brr, locations[permutation[rot][l]][0], locations[permutation[rot][l]][1],
						locations[permutation[rot][l]][2]);
			for (int i = 1; i <= n; i++) {
				int temp = 0;
				for (int j = 1; j <= m; j++)
					temp += brr[i][j];
				if (temp < min)
					min = temp;
			}
		}
		return min;
	}

	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());
		arr = new int[n + 2][m + 2];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= m; j++)
				arr[i][j] = Integer.parseInt(st.nextToken());
		}

		locations = new int[k + 2][3];
		isChecked = new boolean[k + 2];
		int per_size = 1;
		for (int i = 1; i <= k; i++)
			per_size *= i;
		permutation = new int[per_size][k];
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			locations[i][0] = Integer.parseInt(st.nextToken());
			locations[i][1] = Integer.parseInt(st.nextToken());
			locations[i][2] = Integer.parseInt(st.nextToken());
		}
		permutation(0);
		System.out.println(func());
	}
}