BOJ-17406 배열 돌리기 4

필요한 지식

1. 시뮬레이션

2. 조합

3. 완전탐색

접근

1. 연산들의 조합을 구한다.

2. 연산들의 조합이 정해지면 연산을 순서대로 수행한다.

3. 배열 A 값을 업데이트 한다.

4. 모든 연산들의 조합에 따라 반복한다.

per(i) : 1번째 연산의 자리를 찾음. 모든 연산이 자리를 찾을때까지 재귀적으로 탐색하며 연산들의 조합을 구함

go(pi it) : 매개변수로 연산의 정보를 전달하며, 그 연산(시계방향으로 회전) 을 수행함

cal() : 연산을 모두 수행 후 그 배열의 값을 구함

copy() : 연산의 조합이 만들어 질때마다 입력받은 배열값으로 초기화 시킴

코드(C++)

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <vector>
using namespace std;
typedef struct pi {
	int r, c, s;
};
vector<pi>v;
int n, m, k, ans = INT_MAX, map[51][51], tmap[51][51], ttmap[51][51], chk[6];
void copy() {
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) tmap[i][j] = map[i][j];
	return;
}
void cal() {
	int res = INT_MAX;
	for (int i = 1; i <= n; i++) {
		int tmp = 0;
		for (int j = 1; j <= m; j++) {
			tmp += tmap[i][j];
		}
		res = min(res, tmp);
	}
	ans = min(ans, res);
	return;
}
void go(pi it) {
	int t = 1;
	ttmap[it.r][it.c] = tmap[it.r][it.c];
	while (t <= it.s) {
		//위
		for (int x = it.c - t; x < it.c - t + 2 * t; x++) ttmap[it.r - t][x + 1] = tmap[it.r - t][x];
		//아
		for (int x = it.c + t; x > it.c + t - 2 * t; x--) ttmap[it.r + t][x -1] = tmap[it.r + t][x];
		//오
		for (int y = it.r - t; y < it.r - t + 2 * t; y++) ttmap[y+1][it.c+t] = tmap[y][it.c+t];
		//왼
		for (int y = it.r + t; y > it.r + t - 2 * t; y--) ttmap[y-1][it.c-t] = tmap[y][it.c-t];
		t++;
	}
	for (int i = it.r - it.s; i <= it.r + it.s; i++) for (int j = it.c - it.s; j <= it.c + it.s; j++) tmap[i][j] = ttmap[i][j];
	return;
}
void per(int pos) {
	if (pos == k+1) {
		copy();
		for(int i=0;i<k;i++){
			go(v[chk[i]-1]);
		}
		cal();
		return;
	}
	for (int i = 0; i < k; i++) {
		if (!chk[i]) {
			chk[i] = pos;
			per(pos + 1);
			chk[i] = 0;
		}
	}
	return;
}
int main() {
	ios_base::sync_with_stdio(0); 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++) {
		pi tmp; cin >> tmp.r >> tmp.c >> tmp.s;
		v.push_back(tmp);
	}
	per(1);
	cout << ans;
	return 0;
}

next_permutation을 적용한 코드(C++)

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <vector>
using namespace std;
typedef struct pi {
	int r, c, s;
};
vector<pi>v;
vector<int>vv;
int n, m, k, ans = INT_MAX, map[51][51], tmap[51][51], ttmap[51][51];
void copy() {
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) tmap[i][j] = map[i][j];
	return;
}
void cal() {
	int res = INT_MAX;
	for (int i = 1; i <= n; i++) {
		int tmp = 0;
		for (int j = 1; j <= m; j++) {
			tmp += tmap[i][j];
		}
		res = min(res, tmp);
	}
	ans = min(ans, res);
	return;
}
void go(pi it) {
	int t = 1;
	ttmap[it.r][it.c] = tmap[it.r][it.c];
	while (t <= it.s) {
		//상
		for (int x = it.c - t; x < it.c - t + 2 * t; x++) ttmap[it.r - t][x + 1] = tmap[it.r - t][x];
		//하
		for (int x = it.c + t; x > it.c + t - 2 * t; x--) ttmap[it.r + t][x -1] = tmap[it.r + t][x];
		//우
		for (int y = it.r - t; y < it.r - t + 2 * t; y++) ttmap[y+1][it.c+t] = tmap[y][it.c+t];
		//좌
		for (int y = it.r + t; y > it.r + t - 2 * t; y--) ttmap[y-1][it.c-t] = tmap[y][it.c-t];
		t++;
	}
	for (int i = it.r - it.s; i <= it.r + it.s; i++) for (int j = it.c - it.s; j <= it.c + it.s; j++) tmap[i][j] = ttmap[i][j];
	return;
}
int main() {
	ios_base::sync_with_stdio(0); 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++) {
		pi tmp; cin >> tmp.r >> tmp.c >> tmp.s;
		v.push_back(tmp);
		vv.push_back(i);
	}
	do {
		copy();
		for (int i = 0; i < k; i++) {
			go(v[vv[i]]);
		}
		cal();
	} while (next_permutation(vv.begin(), vv.end()));
	cout << ans;
	return 0;
}

결과(위:next_permutation)