Boj 17470) 배열 돌리기 5

문제

백준 17470

설명

기본적으로 대칭, 회전 이동이 문제처럼 적용이 된다면 4분면을 순서대로 인덱싱할 때 0,1,2,3, 부터 3, 2, 1, 0 까지 총 12가지의 패턴이 나온다. 전체 배열에 대해서 쿼리될 뿐만 아니라 이를 4개로 쪼갠 Quat 단위로도 쿼리(5,6 번) 가 나오므로 총 144 개의 패턴 중 하나가 답이 된다.

다음 문제는 144의 패턴을 어떻게 구할 것인가이다. 90도 회전시 정방배열이 아니라서 배열의 행렬의 크기가 바뀌므로 더 까다롭다. 다행히도 이는 위 코드처럼 시작위치랑 오프셋단위를 이용해서 쉽게 구현할 수 있다.

시간 복잡도

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

코드

int arr[101][101], quat[5][51][51];
int n, m, hn, hm;

/*
  0 1   1 2   2 1   4 3
  3 2   3 4   4 3   2 1
*/
int QNum[4] = { 0, 1, 2, 3 }, TNum[4] = { 0, 1, 2, 3 }; // Quat 단위 인덱스, 전체에 대한 인덱스

inline void QUD() {
    swap(QNum[0], QNum[3]);
    swap(QNum[1], QNum[2]);
}
inline void QLR() {
    swap(QNum[0], QNum[1]);
    swap(QNum[3], QNum[2]);
}
inline void TUD() {
    swap(TNum[0], TNum[3]);
    swap(TNum[1], TNum[2]);
}
inline void TLR() {
    swap(TNum[0], TNum[1]);
    swap(TNum[3], TNum[2]);
}
void R(int* arr, int bR) {
    if (bR > 0) {
        int tmp = arr[3];
        arr[3] = arr[2];
        arr[2] = arr[1];
        arr[1] = arr[0];
        arr[0] = tmp;
    }
    else {
        int tmp = arr[0];
        arr[0] = arr[1];
        arr[1] = arr[2];
        arr[2] = arr[3];
        arr[3] = tmp;
    }
}
inline int Offset(int in) { return in > 0 ? 1 : in == 0 ? 0 : -1; }

void Apply()
{
    const pair<int, int> pivots[] = { {0, 0},{hm - 1, 0}, {hm - 1, hn - 1}, {0, hn - 1} };
    bool bXYR = Offset(pivots[QNum[3]].first - pivots[QNum[0]].first);

    // Quat 내부 Rotation 처리
    for (int nq = 0; nq < 4; nq++)
    {
        copy(quat[nq][0], quat[nq][51], quat[4][0]);

        const int bx = pivots[QNum[0]].first;
        const int by = pivots[QNum[0]].second;
        const int oix = Offset(pivots[QNum[3]].first - pivots[QNum[0]].first);
        const int oiy = Offset(pivots[QNum[3]].second - pivots[QNum[0]].second);
        const int ojx = Offset(pivots[QNum[1]].first - pivots[QNum[0]].first);
        const int ojy = Offset(pivots[QNum[1]].second - pivots[QNum[0]].second);

        int x = bx, y = by;
        for (int i = 0; i < (oix ? hm : hn); i++, x += oix, y += oiy)
        {
            for (int j = 0; j < (ojx ? hm : hn); j++, x += ojx, y += ojy)
                quat[nq][i][j] = quat[4][y][x];
            if (ojx) x = bx;
            if (ojy) y = by;
        }
    }

    // Quat 단위 Rotation 처리하면서 원래 배열에 값 넣음
    if (!bXYR)
    {
        for (int i = 0; i < hn; i++)
            for (int j = 0; j < hm; j++)
            {
                arr[i][j] = quat[TNum[0]][i][j];
                arr[i][j + hm] = quat[TNum[1]][i][j];
                arr[i + hn][j + hm] = quat[TNum[2]][i][j];
                arr[i + hn][j] = quat[TNum[3]][i][j];
            }
    }
    else {
        for (int i = 0; i < hm; i++)
            for (int j = 0; j < hn; j++)
            {
                arr[i][j] = quat[TNum[0]][i][j];
                arr[i][j + hn] = quat[TNum[1]][i][j];
                arr[i + hm][j + hn] = quat[TNum[2]][i][j];
                arr[i + hm][j] = quat[TNum[3]][i][j];
            }
    }

    // Print
    for (int i = 0; i < (!bXYR ? n : m); i++)
    {
        for (int j = 0; j < (bXYR ? n : m); j++)
            cout << arr[i][j] << ' ';
        cout << endl;
    }
    cout << endl;
}

int main()
{
    int r;
    cin >> n >> m >> r;
    hn = n / 2, hm = m / 2;

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

    // Quat 단위로 다시 복사함
    for (int i = 0; i < hn; i++)
        for (int j = 0; j < hm; j++)
        {
            quat[0][i][j] = arr[i][j];
            quat[1][i][j] = arr[i][j + hm];
            quat[2][i][j] = arr[i + n / 2][j + hm];
            quat[3][i][j] = arr[i + n / 2][j];
        }

    // 쿼리 처리
    while (r--)
    {
        int op; cin >> op;
        switch (op)
        {
        case 1: QUD(); TUD(); break;
        case 2: QLR(); TLR(); break;
        case 3: R(QNum, 1), R(TNum, 1); break;
        case 4: R(QNum, -1), R(TNum, -1); break;
        case 5: R(TNum, 1);  break;
        case 6: R(TNum, -1); break;
        }
    }

    Apply();
}