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

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

순열 + 구현 문제였습니다.

 

풀이방법

 1. 매 연산마다 범위를 계산해 s와 함께 넣어줍니다. x1 : r - s, y1 : c-s, x2 : r + s, y2 : c + s 로 계산한 후 그 점들과 s를 op라는 변수에 vector형태로 넣어줍니다.

 

 2. dfs형태로 모든 형태의 연산 순열을 뽑아냅니다. 한 연산의 순열을 뽑아냈다면 뽑아낸 순열을 comb라는 vector 변수에 저장합니다. 그 후 배열을 돌려줍니다. 돌린 후에 최솟값을 저장합니다.

 

 3. 최솟값을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int board[51][51], boardCopy[51][51],ck[10];
int n, m, k, ans=0x3f3f3f3f;
vector <int> comb;
vector <vector<int>> op;

void rotate(int x1, int y1, int x2, int y2){
    int curVal = boardCopy[x1][y1];
    //상단 우측으로
    for(int i = y1+1; i <= y2; i++)
        swap(curVal,boardCopy[x1][i]);
    //우측 아래로
    for(int i = x1+1; i <= x2; i++)
        swap(curVal,boardCopy[i][y2]);
    //하단 좌측으로
    for(int i = y2-1; i >= y1; i--)
        swap(curVal, boardCopy[x2][i]);
    //좌측 상단으로
    for(int i = x2 - 1; i >= x1; i--)
        swap(curVal, boardCopy[i][y1]);
}

int getMinValFromRow(){
    int minVal = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++){
        int sum = 0;
        for(int j = 1; j <= m; j++) sum += boardCopy[i][j];
        minVal = min(minVal,sum);
    }
    return minVal;
}

void copyBoard(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) {
            boardCopy[i][j] = board[i][j];
        }
    }
}

void dfs(int depth){
    if(depth == k){
        copyBoard();
        for(auto &c : comb){
            vector <int> range = op[c];
            for(int i = 0; i < range[4]; i++)
                rotate(range[0] + i,range[1] + i,range[2] - i,range[3] - i);
        }
        ans = min(ans,getMinValFromRow());
        return;
    }

    for(int i = 0; i < k; i++){
        if(ck[i]) continue;
        ck[i] = 1;
        comb.push_back(i);
        dfs(depth+1);
        comb.pop_back();
        ck[i] = 0;
    }

}

int main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> board[i][j];

    for(int i = 0; i < k; i++){
        int r,c,s,x1,y1,x2,y2;
        cin >> r >> c >> s;
        x1 = r-s;
        y1 = c-s;
        x2 = r+s;
        y2 = c+s;
        op.push_back({x1,y1,x2,y2,s});
    }

    dfs(0);
    cout << ans << '\n';
}