[BOJ] 17406. 배열 돌리기 4

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

회전 연산을 사용하는 모든 경우를 구해주고 배열을 회전시켜줘야 하는 문제이다.

즉, 완전 탐색 + 시뮬레이션이다.

 

 

회전 정보는 구조체로 만들어서 벡터에 저장하여 관리하였다.

그리고 문제에서 (1,1)부터 시작하므로 r과 c 좌표는 각각 1씩 빼주었다.

정답의 최댓값은 행의 최대길이 50 * 칸의 최댓값 100으로 5000정도이지만 그냥 안전하게 10000 정도를 초기값으로 넣어놨다.

 

 

 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

라는 문제 조건에 따라 사용할 회전 연산 순서를 모두 정해준다.

순서를 정할 때마다 새로운 배열을 만들어서 배열을 회전시켜준 상태로 넘겨준다.

그리고 k개 만큼 순서를 모두 정했다면 그때의 배열의 값(행의 합 중 최솟값)을 구해준다.

 

 

회전을 시킬 때는 밑의 그림에서 파란 네모로 묶인 애들을 각각 for문을 사용해서 옮겨줬다.

즉 for문을 4번 사용하여 회전시켰다.

(r-s, c-s)를 시작점으로 배열을 회전시켜줄 건데 이 부분의 값은 따로 빼놓는다.

그리고 첫번째 for문에서 밑의 칸들을 하나하나 올려준다.

그리고 다시 두 번째 for문에서 오른쪽 칸들을 옆으로 하나하나 옮겨준다.

옮겨주다가 맨 윗줄을 이동시켜줄 때는 마지막 칸을 옮기면 안 되고 처음에 빼놨던 (r-s, c-s) 값을 넣어줘야 한다.

 

 

s가 2인 경우에는 2인 경우와 1인 경우 모두 구해줘야 하기 때문에 s 값을 줄여가면서 배열을 모두 돌려주면 된다.

2부터 시작해서 r-2, c-2를 시작점으로 배열을 회전시키고 난 후에 s 값을 1 감소시켜서

다시 r-1, c-1을 시작점으로 다시 배열을 회전시켜주면 된다.

마찬가지로 s가 더 큰 값일 경우에도 s 수만큼 배열을 회전시키면 된다.

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int ans;
int n, m, k;
bool check[6];
 
struct Info {
    int x;
    int y;
    int size;
    Info(int x, int y, int size) : x(x), y(y), size(size) {}
};
 
vector<Info> vt;
 
void move(int index, int map[50][50]) {
    //index번째 회전 연산의 정보를 가져온다.
    int x = vt[index].x;
    int y = vt[index].y;
    int s = vt[index].size;
 
    while (s > 0) {
 
        int tmp = map[x - s][y - s];
 
        //첫번째 열 이동
        for (int i = x - s; i < x + s; i++) {
            map[i][y - s] = map[i + 1][y - s];
        }
 
        //마지막 행 이동
        for (int j = y - s; j < y + s; j++) {
            map[x + s][j] = map[x + s][j + 1];
        }
 
        //마지막 열 이동
        for (int i = x + s; i > x - s; i--) {
            map[i][y + s] = map[i - 1][y + s];
        }
 
        //첫번째 행 이동
        for (int j = y + s; j > y - s + 1; j--) {
            map[x - s][j] = map[x - s][j - 1];
        }
 
        //마지막 칸
        map[x - s][y - s + 1] = tmp;
        s--;
    }
 
}
 
 
void mapcpy(int map[50][50], int newmap[50][50]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            newmap[i][j] = map[i][j];
        }
    }
}
 
 
//각 행의 합 중 최솟값을 구한다.
void calc(int map[50][50]) {
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            sum += map[i][j];
        }
        if (ans > sum) ans = sum;
    }
}
 
 
void solve(int index, int map[50][50]) {
    if (index == k) {
        //회전 연산을 모두 사용하였으면 계산
        calc(map);
        return;
    }
 
 
    for (int i = 0; i < k; i++) {
        //i번을 이미 사용
        if (check[i]) continue;
 
        int newmap[50][50];
        mapcpy(map, newmap);
 
        //사용 표시후에 배열을 회전시킨다.
        check[i] = true;
        move(i, newmap);
 
        //배열을 회전 시킨 상태에서 다음 회전을 사용하는 경우를 구한다.
        solve(index + 1, newmap);
 
        //다른 회전을 사용하는 경우를 위해 다시 사용 표시 없앤다.
        check[i] = false;
 
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> k;
    ans = 10000;
    int map[50][50];
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
 
    int r, c, s;
    for (int i = 0; i < k; i++) {
        cin >> r >> c >> s;
        r--;
        c--;
        vt.push_back(Info(r, c, s));
    }
 
 
    solve(0, map);
 
    cout << ans << '\n';
 
    return 0;
}