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

1.  문제 링크

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

2.  문제

요약

• N x M 크기인 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미합니다.
• 배열은 회전 연산을 수행할 수 있는데, 회전 연산은 세 정수 (r, c, s)로 이루어져 있습니다.
• 가장 왼쪽 윗 칸이 (r - s, c - s), 가장 오른쪽 아랫 칸이 (r + s, c + s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미입니다.
• 회전 연산이 2개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르게 나타납니다.
• 배열 A와 사용 가능한 회전 연산이 주어졌을 때, 회전 연산을 모두 한 번씩 사용하여 배열 A의 값의 최솟값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 50보다 작거나 같은 배열 A의 크기 N, M과 1보다 크거나 같고 6보다 작거나 같은 회전 연산의 개수 K가 주어지고 두 번째 줄부터 N개의 줄에는 배열 A에 들어있는 수 A[i][j]가 주어집니다. N + 2번째 줄부터 K개의 줄에는 회전 연산의 정보 r, c, s가 주어집니다.
• 출력: 첫 번째 줄에 배열 A의 값의 최솟값을 출력합니다.

3.  소스코드

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

public class Main {
	static int N, M, K, answer;
	static int[][] arr, operation;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		K = scanner.nextInt();
		arr = new int[N][M];
		operation = new int[K][3];
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < M; col++)
				arr[row][col] = scanner.nextInt();
		}
		for(int row = 0; row < K; row++) {
			for(int col = 0; col < 3; col++)
				operation[row][col] = scanner.nextInt();
		}
		answer = Integer.MAX_VALUE;
	}
	
	static void solution() {
		int[][] copy = arr.clone();
		func(0, new boolean[K], copy);
		System.out.println(answer);
	}
	
	static void func(int depth, boolean[] visited, int[][] A) {
		if(depth == K) {
			answer = Math.min(answer, findMinSum(A));
			return;
		}
		for(int index = 0; index < K; index++) {
			if(!visited[index]) {
				visited[index] = true;
				func(depth + 1, visited, rotate(A, operation[index]));
				visited[index] = false;
			}
		}
	}
	
	static int findMinSum(int[][] A) {
		int min = Integer.MAX_VALUE;
		for(int row = 0; row < N; row++) {
			int total = 0;
			for(int col = 0; col < M; col++) total += A[row][col];
			min = Math.min(min, total);
		}
		return min;
	}
	
	static int[][] rotate(int[][] A, int[] operate) {
		int startX = operate[0] - operate[2] - 1, startY = operate[1] - operate[2] - 1;
		int endX = operate[0] + operate[2] - 1, endY = operate[1] + operate[2] - 1;
		int[][] rotateArr = new int[N][M];
		for(int row = 0; row < N; row++) rotateArr[row] = A[row].clone();
		while(true) {
			if(startX >= endX && startY >= endY) break;
			rotateOnce(rotateArr, A, startX, startY, endX, endY);
			startX++;
			startY++;
			endX--;
			endY--;
		}
		return rotateArr;
	}
	
	static void rotateOnce(int[][] rotateArr, int[][] A, int startX, int startY, int endX, int endY) {
		for(int col = startY + 1; col <= endY; col++)
			rotateArr[startX][col] = A[startX][col - 1];
		for(int row = startX + 1; row <= endX; row++)
			rotateArr[row][endY] = A[row - 1][endY];
		for(int col = endY - 1; col >= startY; col--)
			rotateArr[endX][col] = A[endX][col + 1];
		for(int row = endX - 1; row >= startX; row--)
			rotateArr[row][startY] = A[row + 1][startY];	
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}