[C++] 백준 17406번: 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

> 풀이

큰 틀은 최대 6개까지 있는 연산을 브루트포스 돌려서 최소값을 얻어오는 식이다. 예를 들어 연산이 3개가 있다고 하면, 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1와 같은 시퀸스의 모든 집합에 대해서 연산을 수행한다.

그 다음으로는 '배열 돌리기'를 구현만 하면 된다. 단, 백트래킹을 이용하므로 반시계방향 회전도 구현해야한다.

 

#include <bits/stdc++.h>
#define INF 5001
using namespace std;

int N, M, K;
int matrix[50][50];
tuple<int, int, int> op[6];
bool isSelected[6];
int minMatrixValue = INF;

void rotateMatrixClockwise(int r, int c, int s) {
	if (s <= 0) return;

	int tmp = matrix[r - s][c - s];
	int i, j;

	// left
	j = c - s;
	for (i = r - s + 1; i < r + s + 1; i++) {
		matrix[i - 1][j] = matrix[i][j];
	}

	// bottom
	i = r + s;
	for (j = c - s + 1; j < c + s + 1; j++) {
		matrix[i][j - 1] = matrix[i][j];
	}

	// right
	j = c + s;
	for (i = r + s - 1; i > r - s - 1; i--) {
		matrix[i + 1][j] = matrix[i][j];
	}

	// top
	i = r - s;
	for (j = c + s - 1; j > c - s; j--) {
		matrix[i][j + 1] = matrix[i][j];
	}

	matrix[r-s][c-s+1] = tmp;
	rotateMatrixClockwise(r, c, s - 1);
}

void rotateMatrixCounterclockwise(int r, int c, int s) {
	if (s <= 0) return;

	int tmp = matrix[r - s][c - s];
	int i, j;

	// top
	i = r - s;
	for (j = c - s + 1; j < c + s + 1; j++) {
		matrix[i][j - 1] = matrix[i][j];
	}

	// right
	j = c + s;
	for (i = r - s + 1; i < r + s + 1; i++) {
		matrix[i - 1][j] = matrix[i][j];
	}

	// bottom
	i = r + s;
	for (j = c + s - 1; j > c - s - 1; j--) {
		matrix[i][j + 1] = matrix[i][j];
	}

	// left
	j = c - s;
	for (i = r + s - 1; i > r - s; i--) {
		matrix[i + 1][j] = matrix[i][j];
	}

	matrix[r - s + 1][c - s] = tmp;
	rotateMatrixCounterclockwise(r, c, s - 1);
}

int getMatrixValue() {
	int res = INF;

	int i, j;
	for (i = 0; i < N; i++) {
		int rowSum = 0;
		for (j = 0; j < M; j++) {
			rowSum += matrix[i][j];
		}
		res = min(res, rowSum);
	}

	return res;
}

void setMinMatrixValueRecursively(int left) {
	if (left == 0) {
		minMatrixValue = min(minMatrixValue, getMatrixValue());
		return;
	}

	int i;
	for (i = 0; i < K; i++) {
		if (isSelected[i]) continue;

		rotateMatrixClockwise(get<0>(op[i]), get<1>(op[i]), get<2>(op[i]));
		isSelected[i] = true;

		setMinMatrixValueRecursively(left - 1);

		rotateMatrixCounterclockwise(get<0>(op[i]), get<1>(op[i]), get<2>(op[i]));
		isSelected[i] = false;
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int i, j;

	// 입력 1
	cin >> N >> M >> K;

	// Matrix 입력 2
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			cin >> matrix[i][j];
		}
	}

	// 입력 3
	for (i = 0; i < K; i++) {
		int r, c, s;
		cin >> r >> c >> s;
		r--; c--;

		op[i] = make_tuple(r, c, s);
	}

	// Solution
	setMinMatrixValueRecursively(K);
	cout << minMatrixValue;

	return 0;
}