[PS 백준 - 1.11] 16926번: 배열 돌리기 1

문제 정보

백준 16926번 - 바로가기

• 난이도: 실버 3
• 알고리즘: 배열

---

코멘트

이번 알고리즘 문제들 중에서 가장 어려웠던 문제였다. 아이디어 떠올리는 것부터가 쉽지 않았다. 내가 생각한 아이디어는 다음과 같다.

1. 배열의 무게중심 구하기
2. 무게중심으로부터 기울기가 +-1인 직선들을 그어 배열의 영역을 4분할하기
3. 위쪽 영역의 원소들은 한칸씩 왼쪽으로 / 오른쪽 영역의 원소들은 한칸씩 위쪽으로 / 아래쪽 영역의 원소들은 한칸씩 오른쪽으로 / 왼쪽 영역의 원소들은 한칸씩 아래쪽으로 옮겨주기

옮기다보면 임의의 한 직선 위의 원소들은 시작과 끝이 동일해 덮어씌워진 수가 다시 복사되는 경우가 있다. 따라서 스타트 지점들을 따로 저장해두고 나중에 다시 불러오는 방법을 사용하였다.

---

소스 코드

#include <iostream>
using namespace std;

void printArr(int** &arr, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << arr[i][j] << ' ';
        }
        cout << endl;
    }
}

void spinArr(int**& arr, int n, int m) {
    // 배열 돌리기
    double CMx, CMy;
    CMx = (m - 1) / 2.0;
    CMy = (n - 1) / 2.0;
    int r = (int)(min(CMx, CMy) + 0.5);

    // 출발 지점 (save Point)
    int* start;
    start = new int[r];
    for (int i = 0; i < r; i++) {
        start[i] = arr[i][i];
    }

    // 맨 위 (한칸 왼쪽으로)
    for (int i = 0; i < CMy; i++) {
        for (int j = i + 1; j < m - i; j++) {
            arr[i][j - 1] = arr[i][j];
        }
    }

    // 오른쪽 (한칸 위로)
    for (int j = m - 1; j > CMx; j--) {
        for (int i = (m - j); i <= n - (m - j); i++) {
            arr[i - 1][j] = arr[i][j];
        }
    }

    // 아래 (한칸 오른쪽으로)
    for (int i = n - 1; i > CMy; i--) {
        for (int j = (m - 1) - (n - i); j >= (n - 1 - i); j--) {

            arr[i][j + 1] = arr[i][j];
        }
    }

    // 왼쪽 (한칸 아래로)
    for (int j = 0; j < CMx; j++) {
        for (int i = n - 1 - (j + 1); i > j; i--) {
            arr[i + 1][j] = arr[i][j];
        }
    }

    // 시작위치 원상복구
    for (int i = 0; i < r; i++) {
        arr[i + 1][i] = start[i];
    }

    delete[] start;
    start = nullptr;
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int** arr;
    int n, m, r;
    cin >> n >> m >> r;

    arr = new int* [n];
    for (int i = 0; i < n; i++) {
        arr[i] = new int[m];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i < r; i++) {
        spinArr(arr, n, m);
    }

    printArr(arr, n, m);

    for (int i = 0; i < n; i++) {
        delete[] arr[i];
        arr[i] = nullptr;
    }
    delete[] arr;
    arr = nullptr;
}