백준 17406번: 배열돌리기4 (C++)

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

배열 돌리기 목록을 꼭 "모두 사용해야 한다"고 했다. 또한 배열을 돌리는 순서에 따라서 결과가 달라지기 때문에, 순열을 사용해서 돌릴 순서를 정해준다.

모든 경우를 다 돌려봐야 하고, 주의할 사항은, 한 순열을 돌린 이후에, 반드시 배열을 원래 상태로 초기화 시켜줘야 한다는 것이다.

배열을 돌릴 때에는, 모든 값을 보존하면서 돌리는 것이 불가능 하다. 돌리는 순서, 방향에 따라서 반드시 모서리중 어느 한 값은 손실이 발생할 수 밖에 없는데, 그 값을 정해서 미리 담아두고, 마지막에 채워주면 된다.

본인은 가장 좌측 상단의 값을 기억해두고, 그 위치를 없어지는 값으로 정했다. 마지막에 그 값이 옮겨가야 할 곳에 넣어주면 된다.

#include<iostream>
#include<limits.h>
struct Spin {
    int r, c, size;
}sp[8];
using namespace std;
 
int R, C, k, m[51][51],tmp[51][51], arr[8];
bool isused[8];
int Min = INT_MAX;
 
void spin(int val) {
    int rr = sp[val].r, cc = sp[val].c, size = sp[val].size;
    for (int l = 1; l <= size; l++) {
        int leftHigh = m[rr - l][cc - l]; //위쪽 변 넣을때 마지막에 넣어주기
        
        for (int row = rr - l; row <= rr + l-1; row++)  //왼쪽 변
            m[row][cc - l] = m[row+1][cc - l];
    
        for (int col = cc - l; col <= cc + l - 1; col++)  //아래쪽 변
            m[rr + l][col] = m[rr + l][col + 1];
        
 
        for (int row = rr + l; row >= rr - l + 1; row--)  //우측 
            m[row][cc + l] = m[row - 1][cc + l];
        
 
        for (int col = cc + l; col >= cc - l + 2; col--)  //상단
            m[rr - l][col] = m[rr - l][col - 1];
        
        m[rr - l][cc - l + 1] = leftHigh; //기억해 놨던 맨 왼쪽 상단 값 넣어줌
    }
    
}
 
void calMin() {
    int inMin = INT_MAX;
    for (int i = 1; i <= R; i++) {
        int Sum = 0;
        for (int j = 1; j <= C; j++) 
            Sum += m[i][j];
        
        if (inMin > Sum) inMin = Sum;
    }
    if (inMin < Min) Min = inMin;
    
}
void init() {
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++)
            m[i][j] = tmp[i][j];
}
void backTracking(int num) {
    if (num == k) {
        for (int i = 0; i < k; i++)
            spin(arr[i]);
        calMin();
        
        init(); //배열 돌리기 이전으로 초기화
        return;
    }
    for (int i = 0; i < k; i++) {
        if (!isused[i]) {
            arr[num] = i;
            isused[i] = true;
            backTracking(num + 1);
            isused[i] = false;
        }
    }
}
int main(void) {
    cin >> R >> C >> k;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> m[i][j];
            tmp[i][j] = m[i][j];
        }
    }
 
    for (int i = 0; i < k; i++) 
        cin >> sp[i].r >> sp[i].c >> sp[i].size;
    
    backTracking(0);
    cout << Min;
    return 0;
}