[백준]배열돌리기4

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

17406번: 배열 돌리기 4

 

순열 부분에서 삽집....을 한 경험이있다... 벡터로 사용해서 벡터의 원소로 접근해야되는데 ㅎ... 순열을 겉햝기 식으로 한결과인듯....ㅠㅠ

그냥 순열로 완전탐색을 해주고는 시뮬레이션으로 해주면 된다 shift에 대한 공부를 할 수있어서 좋았다.

[0 1 2 3 4 5 6] 의 배열을 [1 2 3 4 5 6 0] 으로 오른쪽으로 밀고 싶다면 , 반대 방향 즉 6의 원소부터 진행하는것이다.

6을 오른쪽으로 옮기고, 5를 옮기고 4를 옮기고 ..... . 그리고 그냥 오른쪽으로 미는 것은 i+1에 i를 넣는것이다.

반대로 왼쪽은 i-1에 i를 넣는 것이다.. 

이 두가지 1. 반대 방향의  원소부터 접근해준다.   2. i+1(오른,아래) or i-1(왼쪽,위로) 로 i를 넣는것이다. 를 알면 쉽다.

###시험때 항상 확인할것###

1. r,c의 순서가 x,y로 뒤집혀있는지   

2. ++,++ 혹은 --,-- 를 해줘야하는지!!(0시작 or 1시작)

<<자기가 가는 Shift>>

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
struct INFO {
    int r, c, s;
    INFO() {};
    INFO(int r, int c, int s) :r(r), c(c), s(s) {};
};
 
int N, M, K;
int A[100][100];
int back[100][100];
INFO info[6];
bool isV[6];
vector<int> v;
int ans = 1e9;
 
void ROTATION(int r, int c, int s) {
    int tmp = back[r - s][c + s];
    for (int i = c + s - 1; i >= c - s; i--) back[r - s][i + 1] = back[r - s][i];
    for (int i = r - s + 1; i <= r + s; i++) back[i - 1][c - s] = back[i][c - s];
    for (int i = c - s + 1; i <= c + s; i++)back[r + s][i - 1] = back[r + s][i];
    for (int i = r + s - 1; i >= r - s + 1; i--) back[i + 1][c + s] = back[i][c + s];
    back[r - s + 1][c + s] = tmp;
}
 
void dfs(int len) {
    if (len == K) {
        memcpy(back, A, sizeof(back));
 
        for (int i = 0; i < K; i++) { //v[i]에 원소로 순열의 정보들이 들어있다.
            int r, c, s;
            r = info[v[i]].r, c = info[v[i]].c, s = info[v[i]].s;
            for (int k = 1; k <= s; k++) ROTATION(r, c, k);
        }
        
        for (int i = 0; i < N; i++) {
            int ss = 0;
            for (int j = 0; j < M; j++) ss += back[i][j];
            if (ans >= ss) ans = ss;
        }
        return;
    }
 
    for (int i = 0; i < K; i++) {
        if (isV[i] == false) {
            isV[i] = true;
            v.push_back(i);
            dfs(len + 1);
            isV[i] = false;
            v.pop_back();
        }
    }
}
 
int main()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> A[i][j];
    
    for (int i = 0; i < K; i++) { 
        int r, c, s;
        cin >> r >> c >> s;
        r--, c--; //문제에서 인덱스를 1부터 시작해주었으므로 하나 빼준다!!!!!!!!!
        info[i] = INFO(r, c, s);
    }
 
    dfs(0);
    printf("%d\n", ans);
    return 0;
}
 

 

<<자기에게로 오는 Shift ( 좀 덜 헷갈림 ) >>

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
 
struct INFO {
    int r, c, s;
};
 
int N, M, K, ans = 1e9;
int map[50][50],back[50][50];
INFO info[6];
bool isV[6];
vector<int> v;
 
void Rotation(int r,int c,int s) {
    int tmp = back[r - s][c - s];
    for (int i = r - s; i <= r + s - 1; i++) back[i][c - s] = back[i + 1][c - s];
    for (int i = c - s; i <= c + s - 1; i++) back[r + s][i] = back[r + s][i + 1];
    for (int i = r + s; i >= r - s + 1; i--) back[i][c + s] = back[i - 1][c + s];
    for (int i = c + s; i >= c - s + 1; i--) back[r - s][i] = back[r - s][i - 1];
    back[r - s][c - s + 1] = tmp;
}
 
void dfs(int len) {
    if (len == K) {
        memcpy(back, map, sizeof(back));
        for (int i = 0; i < K; i++) for (int k = 1; k <= info[v[i]].s; k++) Rotation(info[v[i]].r, info[v[i]].c, k);
        for (int i = 0; i < N; i++) {
            int cnt = 0;
            for (int j = 0; j < M; j++) cnt += back[i][j];
            ans = min(ans, cnt);
        }
        return;
    }
 
    for (int i = 0; i < K; i++) {
        if (!isV[i]) {
            isV[i] = true;
            v.push_back(i);
            dfs(len + 1);
            isV[i] = false;
            v.pop_back();
        }
    }
}
 
void solve() {
    dfs(0);
    printf("%d\n", ans);
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> map[i][j];
    for (int i = 0; i < K; i++) {
        int r, c, s;
        cin >> r >> c >> s;
        r--, c--;
        info[i] = { r,c,s };
    }
    solve();
    return 0;
}