백준 17406 배열 돌리기 4 C++

단순히 손이 많이 가는 백트래킹

배열을 돌릴 순서를 정하고, 배열을 돌리면 된다.

간단한 해설

배열을 돌릴 순서를 정하는 법

단순히 백트래킹 기법을 이용한다.

배열을 돌리는 법

c(거리)에 따라서 모든 거리를 동적으로 돌린다. (rotateArray 함수 부분)

만약 거리가 3이면 먼저 거리 1 회전, 그다음 거리 2 회전 그리고 마지막으로 거리 3 회전을 하면 된다.

나머지 디테일은 전부 생구현

내 아이디어 스케치

 

러프하게 구상하고, 좌표 계산만 확실히

 

답

#include <iostream>
#include <vector>
#include <tuple>
#include <deque>
#include <algorithm>
using namespace std;
vector<vector<int>> v(50,vector<int>(50));
deque<int> picker;
int n,m,k,r,c,s;
int ans=987654321;
void rotateArray(vector<vector<int>>& cache,int y,int x,int dis){
    vector<vector<int>> tmpV=cache;
    for(int i=x-dis+1;i<=x+dis;++i){
        tmpV[y-dis][i]=cache[y-dis][i-1];
    }
    for(int i=y-dis+1;i<=y+dis;++i){
        tmpV[i][x+dis]=cache[i-1][x+dis];
    }
    for(int i=x+dis-1;i>=x-dis;--i){
        tmpV[y+dis][i]=cache[y+dis][i+1];
    }
    for(int i=y+dis-1;i>=y-dis;--i){
        tmpV[i][x-dis]=cache[i+1][x-dis];
    }
    cache=tmpV;
}
void pick(vector<tuple<int,int,int>>& item,vector<bool>& visited,int gae){
    if(gae==k){
        vector<vector<int>> cache(n,vector<int>(m));
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                cache[i][j]=v[i][j];
            }
        }

        for(int i=0;i<k;++i){
            for(int j=1;j<=get<2>(item[picker[i]]);++j){
                rotateArray(cache,get<0>(item[picker[i]]),get<1>(item[picker[i]]),j);
            }
        }
        for(int i=0;i<n;++i){
            int tmp=0;
            for(int j=0;j<m;++j){
                tmp+=cache[i][j];
            }
            ans=min(ans,tmp);
        }
        return;
    }
    for(int i=0;i<k;++i){
        if(!visited[i]){
            visited[i]=true;
            picker.push_back(i);
            pick(item,visited,gae+1);
            visited[i]=false;
            picker.pop_back();
        }
    }
}


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m>>k;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin>>v[i][j];
        }
    }
    vector<tuple<int,int,int>> item(k);
    for(int i=0;i<k;++i){
        cin>>r>>c>>s;
        --r;
        --c;
        item[i]={r,c,s};
    }
    vector<bool> visited(k,false);
    pick(item,visited,0);
    cout<<ans;
}