17406번: 배열 돌리기 4

• 세로 N칸, 가로 M칸의 배열 A가 주어진다.
• A의 값은 각 행의 합 중 최솟값을 의미한다.
• 회전 연산을 순서를 정해 모두 한 번씩 수행한 뒤, A의 값의 최솟값을 구하라.
• 회전 연산은 (r, c, s) 형태이며, 중심이 (r, c)이고 반지름이 s인 정사각형 영역을 시계 방향으로 한 칸씩 돌린다.
• 배열의 크기는 3이상 50이하.
• 회전 연산 횟수는 6번 이하.
• 회전 연산은 언제나 배열 크기 이내에서 수행된다.

접근

시간복잡도

회전 연산이 6번 이하이므로 순열과 비트연산을 사용하면 6! = 720.
배열 자체 크기가 최대인 50일 때, 회전연산을 최대로 수행한다고 생각하면 50 + 복원시, 50 총 100.
어림잡아 10만 언저리의 연산횟수를 짐작할 수 있다.

회전 연산

배열의 외곽부터 한줄씩 회전 시킨다.
여기서 둘레(size)를 매개변수로 넘겨주면 재귀방식으로 구현할 수 있다.
또한, 백트래킹 문제이기에 복원을 위한 반시계 회전 함수도 만들어야한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		input(in);
		solve();	
	}
	
	static int height;
	static int width;
	static int rotate;
	static int[][] matrix;
	static int[][] rotation;
	static int full;
	static int min;
	static void input(BufferedReader in) throws IOException {
		StringTokenizer tokens = new StringTokenizer(in.readLine());
		
		height = Integer.parseInt(tokens.nextToken());
		width = Integer.parseInt(tokens.nextToken());
		rotate = Integer.parseInt(tokens.nextToken());
		
		matrix = new int[height][width];
		rotation = new int[rotate][3];
		
		for(int i = 0; i < height; i++) {
			tokens = new StringTokenizer(in.readLine());
			for(int j = 0; j < width; j++) {
				matrix[i][j] = Integer.parseInt(tokens.nextToken());
			}
		}
		
		for(int i = 0; i < rotate; i++) {
			tokens = new StringTokenizer(in.readLine());
			for(int j = 0; j < 3; j++) {
				rotation[i][j] = Integer.parseInt(tokens.nextToken());
			}
		}
		full = (1<<rotate)-1;
		min = Integer.MAX_VALUE;
	}
	
	static void solve(){
		rotate(0);
		System.out.println(min);
	}
	
	static void rotate(int check) {
		if(check == full) {
			findMin();
			return;
		}
		
		for(int i = 0; i < rotate; i++) {
			if((check & (1 << i)) > 0) continue;
			
			int row = rotation[i][0]-1;
			int col = rotation[i][1]-1;
			int size = rotation[i][2];
			
			rotateClockwise(row, col, size);
			rotate(check | (1 << i));
			rotateCounterClock(row, col, size);
		}
	}
	
	static void printMatrix() {
		for(int i = 0; i < height; i++) {
			for(int j = 0; j < width; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	static void findMin() {
		for(int i = 0; i < height; i++) {
			int sum = 0;
			for(int j = 0; j < width; j++) {
				sum += matrix[i][j];
			}
			min = Math.min(min, sum);
		}
	}
	
	static void rotateClockwise(int row, int col, int size) {
		if(size == 0) return;
		
		int left = col-size;
		int right = col+size;
		int top = row-size;
		int bottom = row+size;
		
		int temp = matrix[top][left];
		
		for(int i = left+1; i <= right; i++) {
			int cur = matrix[top][i];
			matrix[top][i] = temp;
			temp = cur;
		}
		for(int i = top+1; i <= bottom; i++) {
			int cur = matrix[i][right];
			matrix[i][right] = temp;
			temp = cur;
		}
		for(int i = right-1; i >= left; i--) {
			int cur = matrix[bottom][i];
			matrix[bottom][i] = temp;
			temp = cur;
		}
		for(int i = bottom-1; i >= top; i--) {
			int cur = matrix[i][left];
			matrix[i][left] = temp;
			temp = cur;
		}
		rotateClockwise(row, col, size-1);
	}
	
	static void rotateCounterClock(int row, int col, int size) {
		if(size == 0) return;
		
		int left = col-size;
		int right = col+size;
		int top = row-size;
		int bottom = row+size;
		
		int temp = matrix[top][left];
		
		for(int i = top+1; i <= bottom; i++) {
			int cur = matrix[i][left];
			matrix[i][left] = temp;
			temp = cur;
		}
		for(int i = left+1; i <= right; i++) {
			int cur = matrix[bottom][i];
			matrix[bottom][i] = temp;
			temp = cur;
		}
		for(int i = bottom-1; i >= top; i--) {
			int cur = matrix[i][right];
			matrix[i][right] = temp;
			temp = cur;
		}
		for(int i = right-1; i >= left; i--) {
			int cur = matrix[top][i];
			matrix[top][i] = temp;
			temp = cur;
		}
		
		rotateCounterClock(row, col, size-1);
	}
}

회고

• 백트래킹 문제의 경우, 생각보다 브루트포스로 푸는 경우가 많은듯하다.
• 특히나 다소 복잡한 구현이 필요해보이는 경우, 시간복잡도를 계산해보는 습관을 들이는 것이 좋아보인다.