Boj 20328) 배열 돌리기 7

문제

백준 20328

설명

주어진 쿼리를 수행해도 같은 l 의 부분배열은 같은 배치를 공유한다는 것만 알아차리면 쉽게 풀 수 있는 문제이다.

구현도 재귀함수로 쉽게 구현할 수 있어 난이도가 배열 돌리기 5 보다 낮다고 생각한다.

시간 복잡도

O(\(2^{\mathrm{N}+1} + \mathrm{N}\mathrm{R}\))

코드

int arr[1024][1024], cpys[4][512][512];
int n;
/*
  0 1   1 2   2 1   4 3
  3 2   3 4   4 3   2 1
*/
int QNum[10][4];

inline void UD(int* q) {
    swap(q[0], q[3]);
    swap(q[1], q[2]);
}
inline void LR(int* q) {
    swap(q[0], q[1]);
    swap(q[3], q[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;
    }
}

void Apply(int lv, int xo, int yo)
{
    if (lv < 0) return;

    // 4분면을 복사하고
    int w = 1 << lv;
    for (int i = 0; i < w; i++)
        for (int j = 0; j < w; j++)
        {
            cpys[0][i][j] = arr[i+yo][j+xo];
            cpys[1][i][j] = arr[i+yo][j+xo+w];
            cpys[2][i][j] = arr[i+yo+w][j+xo+w];
            cpys[3][i][j] = arr[i+yo+w][j+xo];
        }

    // 가야하는 4분면으로 배치
    for (int i = 0; i < w; i++)
        for (int j = 0; j < w; j++)
            arr[i + yo][j + xo] = cpys[QNum[lv][0]][i][j];

    for (int i = 0; i < w; i++)
        for (int j = 0; j < w; j++)
            arr[i + yo][j + xo + w] = cpys[QNum[lv][1]][i][j];

    for (int i = 0; i < w; i++)
        for (int j = 0; j < w; j++)
            arr[i + yo + w][j + xo + w] = cpys[QNum[lv][2]][i][j];

    for (int i = 0; i < w; i++)
        for (int j = 0; j < w; j++)
            arr[i + yo + w][j + xo] = cpys[QNum[lv][3]][i][j];

    Apply(lv - 1, xo, yo);
    Apply(lv - 1, xo+w, yo);
    Apply(lv - 1, xo+w, yo+w);
    Apply(lv - 1, xo, yo+w);
}

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

    // Initialize
    for (int i = 0; i < n; i++)
    {
        QNum[i][0] = 0;
        QNum[i][1] = 1;
        QNum[i][2] = 2;
        QNum[i][3] = 3;
    }

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

    // Query
	while (r--)
	{
		int k, l;
		cin >> k >> l;
        switch (k)
        {
        case 1: for(int i = 0; i < l; i++) UD(QNum[i]); break;
        case 2: for(int i = 0; i < l; i++) LR(QNum[i]); break;
        case 3: for(int i = 0; i < l; i++) R(QNum[i], 1); break;
        case 4: for(int i = 0; i < l; i++) R(QNum[i], -1); break;
        case 5: for(int i = l; i < n; i++) UD(QNum[i]); break;
        case 6: for(int i = l; i < n; i++) LR(QNum[i]); break;
        case 7: for (int i = l; i < n; i++) R(QNum[i], 1); break;
        case 8: for (int i = l; i < n; i++) R(QNum[i], -1); break;
        }
	}

    Apply(n-1, 0, 0);

    // Print
    for (int i = 0; i < (1 << n); i++)
    {
        for (int j = 0; j < (1 << n); j++)
            cout << arr[i][j] << ' ';
        cout << endl;
    }
}