59 asked

0

아닙니다 큰돌님! 제 질문에 많은 시간 써주셔서 감사합니다..!! 큰돌님 풀이를 최대한 똑같이 이해하는 방향으로 해당 문제 해결해보겠습니다! 항상 감사드려요 :)

0

안녕하세요 자르트님 ㅎㅎ

제가 이 코드 사실 여러번 디버깅을 해봤는데요..

잘 모르겠습니다..

잘 돌려지고 min_y, max_y 하신것도 괜찮습니다.

다만 걸리는 것은 ret을 해당 테스트케이스마다 최솟값으로 하는게 맞아서.

1 경우의 수 중 min > 1a

2 경우의 수 중 min > 2a

...

min(1a, 2a..) 를 출력하는 문제라 이 코드가 옳긴 옳은데요. (ret, ret2 분리)

#include<bits/stdc++.h>
using namespace std;

struct triple {
    int r, c, s;
};
int min_y;
int max_y;
int min_x;
int max_x;
int dir;
int n, m, k, ret = 987654321, ret2 = 987654321;
vector<triple> v;
vector<int> idx;
int a[54][54];
int origin[54][54];
// 위 오른쪽 아래 왼쪽
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
vector<pair<int, int>> vv;

void print(int arr[54][54]) {
    cout << '\n';
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
}

void go(int y, int x) {
    if (x == max_x && y == min_y)dir++;
    if (x == min_x && y == max_y)dir++;
    if (x == max_x && y == max_y)dir++;
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    if (!(min_y <= ny && ny <= max_y && min_x <= nx && nx <= max_x))return;
    vv.push_back({ ny,nx });
    go(ny, nx);
}

void _rotate() {
    while (min_y != max_y) {
        int startY = min_y;
        int startX = min_x;
        dir = 0;
        vv.push_back({ startY,startX });
        go(startY, startX); 
        vv.pop_back();
        vector<int> b;
        for (pair<int, int>p : vv)b.push_back(a[p.first][p.second]);
        rotate(b.rbegin(), b.rbegin() + 1, b.rend());
        int cnt = 0;
        for (pair<int, int>p : vv)a[p.first][p.second] = b[cnt++];
        vv.clear();
        min_x++; max_x--; min_y++; max_y--;
    }
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < m; j++) {
            sum += a[i][j];
        }
        ret = min(ret, sum);
    }
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)cin >> a[i][j];
    }
    memcpy(origin, a, sizeof(origin));
    for (int i = 0; i < k; i++) {
        triple t; cin >> t.r >> t.c >> t.s;
        idx.push_back(i);
        v.push_back(t);
    }
    do {
        ret = 987654321;
        for (int i = 0; i < v.size(); i++) {
             min_y = v[idx[i]].r - v[idx[i]].s - 1;
             max_y = v[idx[i]].r + v[idx[i]].s - 1;
             min_x = v[idx[i]].c - v[idx[i]].s - 1;
             max_x = v[idx[i]].c + v[idx[i]].s - 1;
            _rotate();
        }
        ret2 = min(ret2, ret);
        print(a);
        memcpy(a, origin, sizeof(a));

    } while (next_permutation(idx.begin(), idx.end()));
    cout << ret2 << '\n'; 
    
}

이것도 틀렸다고 나오네요..

도움이 못되어서 죄송합니다.

감사합니다.