16926/16927 : 배열돌리기 1/2

formula

배열에서 경로가 연속으로 정해진 경로
(정해진 경로에서 순환하는 경우)

배열의 값이 아니라 좌표를 1D array에 저장 후 한 번에 옮길 수 있음

경로의 좌표를 순서대로 1D Array에 저장하고 방향에 따라 밀어주기로 하면 됨

하나하나 밀어주는거보다 이게 실수도 적고 시간초과 문제도 없음

---

2차원 배열의 좌표를 1차원으로 옮겨 밀어버리고 값을
다시 2차원 배열로 옮기는 방식 사용
단 정해진 고정경로 회전시

---

• 1D로 원본 내용 이동

int er = sr + n - 1;
int ec = sc + m - 1;

int idx = 0;

// 1. 위 (왼쪽 -> 오른쪽)
for (int c = sc; c <= ec; c++) arr[idx++] = { sr, c };
// 2. 오른쪽 (위 -> 아래)
for (int r = sr + 1; r <= er; r++) arr[idx++] = { r, ec };
// 3. 아래 (오른쪽 -> 왼쪽)
for (int c = ec - 1; c >= sc; c--) arr[idx++] = { er, c };
// 4. 왼쪽 (아래 -> 위)
for (int r = er - 1; r >= sr + 1; r--) arr[idx++] = { r, sc };

• R번 회전

(i - R) % idx // idx 나머지 연산 필수

//음수 보정으로 원래 위치로
if(newidx < 0) newidx += idx;

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 305
int N, M, R;
int matrix[MAX][MAX];
int temp[MAX][MAX];

struct RC {
    int r;
    int c;
};

RC arr[MAX * MAX];

void copyMap() {
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= M; c++) {
            temp[r][c] = matrix[r][c];
        }
    }
}

void rotateStep(int sr, int sc, int n, int m) {
    int er = sr + n - 1;
    int ec = sc + m - 1;

    int idx = 0;

    // 1. 위 (왼쪽 -> 오른쪽)
    for (int c = sc; c <= ec; c++) arr[idx++] = { sr, c };
    // 2. 오른쪽 (위 -> 아래)
    for (int r = sr + 1; r <= er; r++) arr[idx++] = { r, ec };
    // 3. 아래 (오른쪽 -> 왼쪽)
    for (int c = ec - 1; c >= sc; c--) arr[idx++] = { er, c };
    // 4. 왼쪽 (아래 -> 위)
    for (int r = er - 1; r >= sr + 1; r--) arr[idx++] = { r, sc };

    // 1D 덮어쓰기
    for (int i = 0; i < idx; i++) {
        int newIndex = (i - R) % idx; // R번 시프트
        if (newIndex < 0) newIndex += idx; // 음수 보정

        RC front = arr[newIndex];
        // 1D shift를 overwrite
        matrix[front.r][front.c] = temp[arr[i].r][arr[i].c];
    }
}

void rotate() {
    copyMap();

    int sr = 1, sc = 1;
    int n = N, m = M;
    int step = min(N, M) / 2; // 테두리 개수

    for (int s = 0; s < step; s++) {
        rotateStep(sr, sc, n, m);
        sr++; sc++;     // 시작점 축소
        n -= 2; m -= 2; // 가로세로 길이 축소
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> R;

    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= M; c++) {
            cin >> matrix[r][c];
        }
    }

    rotate();

    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= M; c++) {
            cout << matrix[r][c] << " ";
        }
        cout << "\n";
    }

    return 0;
}