[백준] 배열 돌리기 4

배열 돌리기 시리즈가 굉장히 많은데 이미 블로그에 포스팅을 했던 리트코드 Spiral Matrix 시리즈와 유사해서 많이 넘어가다가 몸 풀기로 배열 돌리기 4 문제를 풀어보았다. 문제를 읽는데 생각보다 쉽지 않았고 예전에 내가 풀었던 자료도 참고 해봤는데 잘 못풀었어서 많이 당황 했었다.

이 문제는 회전은 시계방항으로 한번만 하되, 회전을 해야하는 범위를 다양하게 주고 최솟값을 구하기 위해 순서에 상관없는 방법으로 배열 A의 값을 계속 계산해주면 된다.

처음에는 단순하게 배열만 범위내로 돌리면 될까 싶었는데 순서에 상관없는 방법을 보자마자 이건 Permutation 방법으로 풀어야 되겠구나 생각이 바로 들었다.

내가 처음에 너무 실수를 했던 부분이어서 많이 해맸던 파트다. 배열 범위가 주어졌을때 이 배열에 모든 Permutation 을 finalList 에 다 넣고 그 리스트를 탐색하면 되지 않을까 싶었는데 알고보니 dfs 탐색 중에 모두 계산을 해야 맞았다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 100010
using namespace std;

int N, M, K; 
bool visited[7];
vector<vector<int>> matrix; 
vector<vector<int>> copyMatrix;  
vector<vector<int>> rotateList; 
vector<vector<int>> finalList; 
int answer = INT_MAX;

void Input(){
    cin >> N >> M >> K; 
    vector<vector<int>> copy(N+1,vector<int>(M+1,0)); 
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> copy[i][j]; 
        }
    }

    for(int i = 0; i < K; i++){
        int a,b,c; 
        cin >> a >> b >> c; 
        rotateList.push_back({a,b,c}); 
    }
    matrix = copy; 
    copyMatrix = matrix; 
}

int compute(){
    int ret = INT_MAX; 
    for(int i = 1; i <= N; i++){
        int tmp =  0; 
        for(int j =1; j<= M; j++){
            tmp += matrix[i][j]; 
        }
        ret = min(ret,tmp); 
    }
    return ret; 
}

void rotate(int top, int bottom, int left, int right){
    while(left < right && top < bottom){
        int tmp = matrix[top][left]; 
        for(int i = top; i < bottom; i++) matrix[i][left] = matrix[i+1][left];
        for(int j = left; j < right; j++) matrix[bottom][j] = matrix[bottom][j+1];
        for(int i = bottom; i > top; i--) matrix[i][right] = matrix[i-1][right]; 
        for(int j = right; j > left; j--) matrix[top][j] = matrix[top][j-1]; 
        matrix[top][left+1] = tmp;

        left++, top++, bottom--,right--; 
    }
}

void dfs(int cnt){
    if(cnt == K){
        matrix =copyMatrix; 
        for(vector<int>& v : finalList){
            int top = v[0] - v[2]; 
            int bottom = v[0] + v[2]; 
            int left = v[1] - v[2]; 
            int right = v[1] + v[2]; 
            rotate(top,bottom,left,right); 
        }
        int tmp = compute(); 
        answer = min(answer,tmp); 
        return; 
    }
    for(int i = 0; i < rotateList.size(); i++){
        if(!visited[i]){
            visited[i] = true; 
            finalList.push_back(rotateList[i]); 
            dfs(cnt+1); 
            visited[i] = false; 
            finalList.pop_back(); 
        }
    }
}

void Solution(){
    memset(visited,false,sizeof(visited)); 
    dfs(0); 
    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

솔직히 쉽지만은 않은 문제였고 돌리는 과정을 포함해서 Matrix를 리셋해주는 과정까지도 잊지 말아야 했다. 내가 처음 했던 방법도 맞을 법한데 반례가 없어서 틀린 이유를 잘 모르지만 이렇게 하는게 맞다면 이렇게 해야겠다.

배운점:
1. Permutation 을 사용할때 주의하자
2. 문제를 잘 읽자