백준 17406번: 배열 돌리기4

1) 문제분석

  (r,c,s)라는 값이 주어졌을 때, (r,c)를 기준으로 (r-s,c-s)에서 시작해서 (r+s,c+s)에서 끝나는 사각형 안의 배열 값들을 시계 방향으로 한 칸씩 이동시키는 연산이 있다. 배열값은 배열의 각 행의 모든 값들의 합의 최솟값이다. 문제는 주어진 여러 연산이 있을 때, 임의의 순서대로 이 연산들을 수행했을 때 가능한 배열의 최솟값을 구하는 것이다. 잠깐 생각해보았을 때 딱히 좋은 방법이 떠오르지 않는다면 문제에서 요구하는 그대로 우선 코드를 작성해보는게 좋다. 내가 사용한 방법은, (r,c)에서 가장 가까운 사각형에 포함된 원소들 먼저 회전 연산을 수행해 주는 것이다.

  s의 값이 3이라고 한다면, 우선 (r-1,c-1)값을 저장하고 (r-1,c-1) <= (r,c-1) <= (r+1,c-1) , (r+1,c-1) <= (r+1,c) <= (r+1,c-1) 이런 식으로 한 칸씩 값을 이동시켜주고, 마지막으로는 (r-1,c)에 이전에 저장해놓은 (r-1,c-1) 값을 저장한다. 그 다음에는 (r-2,c-2)값을 저장하고 마찬가지로 (r-2,c-2) <= (r-1,c-2) <= (r,c-2) <= (r+1,c-2) <= (r+2,c-2)

이런 식으로 한 칸씩 값을 이동시켜주고 나머지 연산도 위와 똑같이 해준다. (r-3,c-3)에 대해서도 같은 연산을 해주면 비로소 s의 값이 3일 때의 회전 연산이 끝난다.
  문제 자체는 어렵지 않은데 주어진 연산들을 순서가 다르게 수행해보았을 때 연산 수행 전에 배열의 값들을 초기화 시켜주지 않아서 제대로 된 결과가 나오지 않아 채점 시 틀렸었다. 많은 알고리즘 문제에서 변화한 값을 원래 값으로 수정하지 않고 그대로 사용해서 잘못된 결과를 얻는 실수를 하는 것 같다. 항상 이를 의식하고 확인할 수 있도록 노력해야 할 것 같다.

2) 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int matrix[50][50];  //입력 배열
int copy_m[50][50];  //입력 배열 복사배열
int N,M;             //배열의 크기 N*M
int k;               //회전 연산의 개수
int rot[6][3];       //회전 연산 정보
int min_val=1e9;     //배열값의 최솟값
vector<int> order;   //회전 연산 순서


void solve(){
    int r,c,s, temp;
    //가능한 모든 회전 연산 순서의 경우의 수를 따짐
    do{
        //입력 배열을 새로 복사함
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++)
                copy_m[i][j] = matrix[i][j];
        }

        //order 벡터에 저장된 순서대로 회전 연산 수행
        for(int i=0; i<k; i++){
            int o = order[i];
            r=rot[o][0]-1; c=rot[o][1]-1; s=rot[o][2];

            //(r,c)와 가장 가까운 안 쪽 사각형부터 차례로 회전
            for(int v=1; v<=s; v++){
                //현재 사각형의 가장 왼쪽 위의 값 저장
                temp = copy_m[r-v][c-v];

                //왼쪽 열에서 회전
                for(int l=r-v; l<r+v; l++)
                    copy_m[l][c-v] = copy_m[l+1][c-v];
                //아래쪽 행에서 회전
                for(int l=c-v; l<c+v; l++)
                    copy_m[r+v][l] = copy_m[r+v][l+1];
                //오른쪽 열에서 회전
                for(int l=r+v; l>r-v; l--)
                    copy_m[l][c+v] = copy_m[l-1][c+v];
                //위쪽 행에서 회전
                for(int l=c+v; l>c-v+1; l--)
                    copy_m[r-v][l] = copy_m[r-v][l-1];

                copy_m[r-v][c-v+1] =temp;
            }
        }

        //각 행의 합을 구한 뒤 최솟값 구함
        for(int i=0; i<N; i++){
            int sum = 0;
            for(int j=0; j<M; j++)
                sum += copy_m[i][j];
            if(min_val>sum)
                min_val = sum;
        }

    }while(next_permutation(order.begin(), order.end()));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M >> k;

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> matrix[i][j];
        }
    }
    for(int i=0; i<k; i++){
        for(int j=0; j<3; j++)
            cin >> rot[i][j];
    }

    for(int i=0; i<k; i++)
        order.push_back(i);

    solve();
    cout<<min_val;
}