[BOJ] 17406 : 배열 돌리기 4 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. 백트레킹을 통해 입력된 회전 연산에 대해서 가능한 모든 순서 쌍을 정한다.

2. 순서 쌍이 정해지면 Map을 tempMap에 복제해 순서 쌍대로 tempMap에 회전 연산을 진행한다.

3. 회전 연산이 끝나면 RowSum 중에 가장 작은 값을 뽑아 답을 갱신한다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef struct turn {
	int r, c, s;
}turn;

int N, M, K, map[51][51] = {}, ans = 987654321;
turn list[6] = {};
vector<int> v;
bool visited[6] = {};

int getMinRowsum(int tempMap[51][51]) {
	int t = 987654321;
	for (int i = 1; i <= N; i++) {
		int sum = 0;
		for (int j = 1; j <= M; j++)
			sum += tempMap[i][j];
		t = min(sum, t);
	}
	return t;
}

void turnOperation(int tempMap[51][51], int r, int c, int s) {
	for (int i = s; i > 0; i--) {
		int temp = tempMap[r - i][c - i];
		for (int j = -i; j < i; j++)
			tempMap[r + j][c - i] = tempMap[r + j + 1][c - i];
		for (int j = -i; j < i; j++)
			tempMap[r + i][c + j] = tempMap[r + i][c + j + 1];
		for (int j = i; j > -i; j--)
			tempMap[r + j][c + i] = tempMap[r + j - 1][c + i];
		for (int j = i; j > -i + 1; j--)
			tempMap[r - i][c + j] = tempMap[r - i][c + j - 1];
		tempMap[r - i][c - i + 1] = temp;
	}
}

void startTurn(void) {
	int tempMap[51][51] = {};
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			tempMap[i][j] = map[i][j];

	for (int i = 0; i < K; i++)
		turnOperation(tempMap, list[v[i]].r, list[v[i]].c, list[v[i]].s);
	
	ans = min(ans, getMinRowsum(tempMap));
	return;
}

void permutation(int c) {
	if (c == K) {
		startTurn();
		return;
	}
	for(int i = 0; i < K; i++)
		if (visited[i] == false) {
			visited[i] = true;
			v.push_back(i);
			permutation(c + 1);
			v.pop_back();
			visited[i] = false;
		}
	return;
}

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

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> map[i][j];

	for (int i = 0; i < K; i++)
		cin >> list[i].r >> list[i].c >> list[i].s;

	permutation(0);
	cout << ans;

	return 0;
}