백준17406 배열돌리기4

2020.02.16

백준17406 / 배열돌리기4

풀이

• 알고리즘 : 완전탐색 + Simulation

• 전역변수

  • inMap : 초기 배열 A 상태
  • nextMap : 경우의 수에 따라 회전을 진행한 배열 A
  • rotateOrder : K번의 회전을 수행할 때 0 ~ K-1 번째 회전 index를 저장하는 변수
  • checkRotate : 순열을 재귀함수로 구현할 때 이미 사용한 index인지 체크하는 변수
  • rotateInfo, rotateSize : r,c,s로 주어지는 회전정보들을 0 ~ K-1 번에 저장하는 변수

• 함수

  • getMin : 배열A의 최소 크기를 계산하면서 nextMap을 처음 inMap으로 초기화하는 함수
  • getResult : n번~K-1번의 회전정보를 결정하고 simulate 함수를 이용해 배열 A의 최소값을 반환하는 함수
  • simulate : 0번 ~ K-1번의 회전정보를 이용해 nextMap을 회전시키는 함수

코드

//! 2020.02.16
// TODO BJ17406_배열돌리기4
#include<cstdio>
#include<vector>

using namespace std;

const int MAX = 55;
int N,M,K;
int inMap[MAX][MAX];
int nextMap[MAX][MAX];
int rotateOrder[10];                // 0 ~ K-1 : rotate order
bool checkRotate[10];               // 0 ~ k-1 : idx-th rotate number
vector <pair<int,int>> rotateInfo;  // 0 ~ K-1 : rotate center point
vector <int> rotateSize;            // 0 ~ K-1 : rotate box size\

int getMin(){
    int minRet = 987654321;
    for(int i=0;i<N;i++){
        int tmpSum = 0;
        for(int j=0;j<M;j++){
            tmpSum += nextMap[i][j];
            nextMap[i][j] = inMap[i][j];
        }
        if(minRet>tmpSum) minRet = tmpSum;
    }
    return minRet;
}

int simulate(){
    for(int k=0;k<K;k++){
        int idx = rotateOrder[k];
        int r = rotateInfo[idx].first;
        int c = rotateInfo[idx].second;
        int s = rotateSize[idx];

        int tmpMap[MAX][MAX];
        for(int i=-s;i<=s;i++){
            for(int j=-s;j<=s;j++){
                tmpMap[i+s][j+s] = nextMap[r+i][c+j];
            }
        }
        for(int ss=1;ss<=s;ss++){
            for(int j=c-ss+1;j<=c+ss;j++){
                nextMap[r-ss][j] = tmpMap[s-ss][j-c+s-1];
                nextMap[r+ss][j-1] = tmpMap[s+ss][j-c+s];
            }
            for(int i=r-ss;i<=r+ss-1;i++){
                nextMap[i][c-ss] = tmpMap[i-r+s+1][s-ss];
                nextMap[i+1][c+ss] = tmpMap[i-r+s][s+ss];
            }
        }
    }
    return getMin();
}

int getResult(int idx){
    if(idx>=K){
        return simulate();
    }else{
        int minResult = 987654321;
        for(int i=0;i<K;i++){
            if(!checkRotate[i]){
                checkRotate[i] = true;
                rotateOrder[idx] = i;
                int tmpResult = getResult(idx+1);
                checkRotate[i] = false;
                if(minResult>tmpResult) minResult = tmpResult;
            }
        }
        return minResult;
    }
}

int main(){
    scanf("%d %d %d",&N,&M,&K);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf("%d",&inMap[i][j]);
            nextMap[i][j] = inMap[i][j];
        }
    }
    for(int i=0;i<K;i++){
        int r,c,s;
        scanf("%d %d %d",&r,&c,&s);
        rotateInfo.push_back(make_pair(r-1,c-1));
        rotateSize.push_back(s);
    }

    printf("%d\n",getResult(0));
    return 0;
}

실수

simulate 함수를 구현할 때 tmpMap을 사용하지 않고 그냥 inMap을 사용하였었는데 회전이 여러번 있는 경우에 이렇게 하게 되면 nextMap에 계속 그때그때 한번의 회전만 반영된 결과가 저장되는 문제가 생겼다.

nextMap 만 가지고 덮어쓰는 방식으로 구현하게 되면 for loop를 수행하는 순서를 좀더 세밀하게 조정하는 방법이 있었다.

하지만 좀더 빠르게 문제를 해결하기 위해 메모리 여유를 이용해서 tmpMap으로 그때그때 회전시키는 부분의 nextMap(이전 회전을 수행한 Map)을 받아와서 이용하는 방법으로 해결했다.

처음 구현해둔 for loop들을 그대로 사용하려 하다보니 tmpMap의 index가 약간 더럽게 되었지만 문제를 해결할 수 있었다.