입력
map에 배열을 입력받고, 회전 연산의 정보는 따로 벡터에 담았다. 벡터에 구조체로 넣어서 하려고 했는데, 3개 이상의 값을 구조체에 넣으면 크기 순으로 따로 정렬을 해야되고 귀찮아서 vector<pair<pair<int, int>,int>>v; 로 때려박았다
구현
구현은 3가지를 중점적으로 생각했다.
- 연산에 맞게 배열을 회전시키기 --> rotate 함수 사용
- 연산의 순서를 정하기 --> next_permutation 사용
- 각 행별로 더하기 --> calc 함수 사용
우선, rotate 함수의 구현은 다음과 같다.
배열을 움직여야 하므로 backup 배열에 memcpy 해두었다.
움직이는 것은 정사각형으로 움직이므로 좌상단, 우상단의 좌표를 저장해두고 그에 맞게 배열을 이동했다.
예를들어 5x5 정사각형이 이동해야하면, 가장 바깥쪽의 정사각형 라인이 움직이고 그 안쪽에 있는 3x3 정사각형도 움직여야 한다.
while loop을 돌며 좌상단과 우하단의 좌표가 같아지면 1x1 정사각형이다.
즉, 가장 안쪽에 있는 정사각형에 도달한 것이므로 이동이 끝났음을 의미한다. break로 탈출한다.
연산의 순서를 정하는 것은 next_permutation을 사용했다.
next_permutation은 조사하는 배열의 크기가 20정도만 되어도 시간초과의 위험이 있지만 K가 최대 6이므로 시간초과의 위험은 없다.
벡터에 입력받은 회전 연산에 대해 순열을 구했다. 이 값을 rotate 함수에 인자값으로 넘겨주어 rotate 함수에서 좌상단, 우하단 좌표 값을 계산할 수 있다.
next_permutation 은 정렬된 리스트에만 적용할 수 있으므로 벡터를 정렬해주는것이 중요하다. 어차피 순열만 구하면 되기 때문에 크기순으로 정렬이 되든, 역순으로 정렬이 되든 큰 상관이 없다.
마지막으로 각 행별로 더하여 최소값을 찾는 것은 크게 어렵지 않다.
연산의 순서에 맞게 rotate 함수가 끝나고 최종적으로 이동이 완료된 배열을 각 행별로 더해가며 최소값을 구하고 그 값을 return 해주면 된다
소스코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#define MAX 51
using namespace std;
int n, m, k;
int r, c, s;
int map[MAX][MAX];
int backup[MAX][MAX];
int tmp_backup[MAX][MAX];
vector<pair<int,pair<int, int>>>v;
int calc() { // 행의 합들 중 최솟값
int res = 987654321;
for (int i = 1; i <= n; i++) {
int cur = 0;
for (int j = 1; j <= m; j++) {
cur += backup[i][j];
}
res = min(cur, res);
}
return res;
}
void rotate(int R,int C,int S) {
memcpy(tmp_backup, backup, sizeof(tmp_backup));
int left_y = R - S; int left_x = C - S;
int right_y = R + S; int right_x = C + S;
while (true) {
// 오른쪽으로 진행
for (int j = left_x; j < right_x; j++) {
backup[left_y][j + 1] = tmp_backup[left_y][j];
}
// 아래쪽으로 진행
for (int i = left_y; i < right_y; i++) {
backup[i + 1][right_x] = tmp_backup[i][right_x];
}
// 왼쪽으로 진행
for (int j = right_x; j > left_x; j--) {
backup[right_y][j - 1] = tmp_backup[right_y][j];
}
// 위쪽으로 진행
for (int i = right_y; i > left_y; i--) {
backup[i - 1][left_x] = tmp_backup[i][left_x];
}
// 배열의 안쪽도 진헹
left_y++; left_x++; right_y--; right_x--;
// 정사각형이므로, 가운데 점에 도착하면 끝
if ((left_y == right_y) && (left_x == right_x)) {
break;
}
}
}
int main() {
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 >> r >> c >> s;
v.push_back({ r,{c,s} });
}
sort(v.begin(),v.end());
int result = 987654321;
do
{
memcpy(backup, map, sizeof(backup));
for (int i = 0; i < v.size(); i++) {
rotate(v[i].first, v[i].second.first, v[i].second.second);
}
result = min(calc(), result);
} while (next_permutation(v.begin(), v.end()));
cout << result;
}