Boj 16927) 배열 돌리기 2

문제

백준 16927

설명

회전은 중심으로 부터 거리가 같은 원소들이 이루는 직사각형에서 이루어진다. 이는 min(n, m)/2 개 만큼 존재한다. 중심으로부터 거리가 먼 곳부터 차례대로 회전시킨다.

이때 회전의 편의성을 위해 같은 회전 직사각형의 원소들을 선형으로 묶어서 한번에 계산했다.

시간 복잡도

O(\(\mathrm{N}\mathrm{M}\))

코드

int arr[301][301];
int n, m, r;
vector<int*> linears; vector<int> copys;

void Linearize(int p = 0)
{
    if (p << 1 >= min(n, m)) return;

    for (int i = p; i < n - p - 1; i++)
        linears.push_back(&arr[i][p]);

    for (int i = p; i < m - p - 1; i++)
        linears.push_back(&arr[n-p-1][i]);
 
    for (int i = n - p - 1; i > p; i--)
        linears.push_back(&arr[i][m-p-1]);

    for (int i = m - p - 1; i > p; i--)
        linears.push_back(&arr[p][i]);

    for (int* i : linears)
        copys.push_back(*i);
 
    int total = linears.size();
    int j = (total - r % total) % total;
    for (int i = 0; i < total; i++)
    {
        *linears[i] = copys[j++];
        if (j == total) j = 0;
    }
    linears.clear();   copys.clear();

    Linearize(p + 1);
}

int main()
{
    cin >> n >> m >> r;

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

    Linearize();

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