[BOJ] 배열 돌리기4

[문제]

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

17406번: 배열 돌리기 4

[풀이]

17406

맞았습니다!!

2008

8

C++14 / 수정

2425

43초 전

 

0) 조합 + 단순 반복?

 

1) next_permutation을 사용해서 연산 순서 조합을 구한 후에 배열을 회전시킨다. 

 

2) 회전이 끝나면 각 행의 값을 구한다.

 

3) 최소값을 구한다. 

 

---

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
//풀이 시간 : 40분 
int n, m, k, map[51][51], ans = 987654321;
 
typedef pair<int, int> pp;
typedef pair<pp, int> ppp;
 
vector<ppp> op;
vector<int> seq;
 
bool visited[7];
 
void printMap() {
     cout << '\n';
     for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << map[i][j] << " ";
        }
        cout << '\n';
    }
     cout << '\n';
}
int rotateArray() {
    for (int z = 0; z < k; ++z) {
        //연산 수대로 진행 
        int r = op[seq[z]].first.first;
        int c = op[seq[z]].first.second;
        int s = op[seq[z]].second;
 
        int cycle = s;
 
        while (cycle > 0) {
            int tmp = map[r - cycle][c - cycle];
 
            //->
            for (int i = c - cycle + 1; i <= c + cycle; i++) {
                int tmp2 = map[r - cycle][i];
                map[r - cycle][i] = tmp;
                tmp = tmp2;
            }
 
            //V
            for (int i = r - cycle + 1; i <= r + cycle; i++ ) {
                int tmp2 = map[i][c + cycle];
                map[i][c+cycle] = tmp;
                tmp = tmp2;
 
            }
 
            //<-
            for (int i = c + cycle-1; i >= c-cycle; i--) {
                int tmp2 = map[r + cycle][i];
                map[r+cycle][i] = tmp;
                tmp = tmp2; 
            }
 
            //^
            for(int i = r + cycle-1; i >= r-cycle; i--) {
                int tmp2 = map[i][c-cycle];
                map[i][c-cycle] = tmp;
                tmp = tmp2;
 
            }
            cycle--;
        }
        // printMap();
    }
    int res = 987654321, sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum = 0;
        for (int j = 1; j <= m; ++j) {
            sum += map[i][j];
        }      
        res = min(sum, res);
 
    }
    return res;
 
}
// void dfs(int cnt, int cur) {
//     if (cnt == op.size()) {
       
//         for (int i = 0; i < seq.size(); i++) {
//             cout << seq[i] << '\n';
//         }
//         int res = rotateArray();
//         ans = min(res, ans);
 
//         return;
//     }
//     visited[cur] = true;
//     seq.push_back(cur);
//     dfs(cnt+1, cur+1 );
//     visited[cur] = false;
//     seq.pop_back();
 
//     // for (int i = cur; i < op.size(); ++i) {
//     //     if (!visited[i]) {
//     //         visited[i] = true;
//     //         seq.push_back(i);
//     //         dfs(cnt+1, cur+1);
//     //         seq.pop_back();
//     //         visited[i] = false;
//     //     }
//     // }
// }
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < k; ++i) {
        int a, b, c;
 
        cin >> a >> b >> c;
 
        op.push_back(ppp(pp(a, b), c));
        seq.push_back(i);
 
    }
    //input 
 
    // dfs(0,0);
    //연산 순서를 정한다. 
 
    do {
        int c_map[51][51];
 
        memcpy(c_map, map, sizeof(map));
 
        ans = min(ans, rotateArray());
 
        memcpy(map, c_map, sizeof(map));
 
    } while(next_permutation(seq.begin(), seq.end()));
 
    cout << ans << '\n';
    return 0;
}