[백준][C++] 20327 배열 돌리기 6

www.acmicpc.net/problem/20327

20327번: 배열 돌리기 6

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    - l에 따라 부분 나누기

        * for문 2개를 이용한다. 아래와 같이 구할 수 있다.

 

               for(int i=0; i<range; i+=len)
                   for(int j=0; j<range; j+=len)

 

    - 연산

        * 1~4번 연산을 구현한다. 코드를 보는 것이 이해가 쉽다.

        * 5~8번 연산은 1~4번 연산을 이용해서 구할 수 있다.

 

 

구현(C++)

#include <iostream>
#include <cstring>
#include <vector>
 
using namespace std;
 
int n, r;
int range;
vector<pair<int, int> > cmd;
 
int mat[130][130];
int mat2[130][130];
 
 
void print(){
    for(int i=0; i<range; i++){
        for(int j=0; j<range; j++){
            cout << mat2[i][j] << " ";
        }
        cout << endl;
    }
}
 
 
// 상하반전  
void work_1(int len){
    int r, c;
    int cnt=0;
    
    // 부분을 나눕니다.  
    for(int i=0; i<range; i+=len){
        for(int j=0; j<range; j+=len){
            // 나눈 부분의 시작점 i와 j에서 끝인 r과 c를 설정합니다.  
            r = i + len;
            c = j + len;
            // 부분으로 설정된 범위만 수행합니다. 
            for(int a=i; a<r; a++){
                for(int b=j; b<c; b++){
                    // len + cnt를 해주어야 범위 안에서 바뀝니다. 
                    mat2[r-1-a + len*cnt][b] = mat[a][b];
                }
            }
        }
        cnt++;
    }
    memcpy(mat, mat2, sizeof(mat2));
}
 
// 좌우반전  
void work_2(int len){
    int r, c;
    int cnt=0;
    
    for(int i=0; i<range; i+=len){
        for(int j=0; j<range; j+=len){
            r = i + len;
            c = j + len;
            for(int a=i; a<r; a++){
                for(int b=j; b<c; b++){
                    mat2[a][c-1-b+len*cnt] = mat[a][b];
                }
            }
            cnt++;
        }
        cnt=0;
    }
    memcpy(mat, mat2, sizeof(mat2));
}
 
// 시계방향 90도  
void work_3(int len){
    int r, c;
    int gap_c=0, gap_r=0;
    int cnt=0;
    
    for(int i=0; i<range; i+=len){
        for(int j=0; j<range; j+=len){
            r = i + len;
            c = j + len;
            for(int a=i; a<r; a++){
                for(int b=j; b<c; b++){
                    // len*gap_r과 len*cnt 그리고 len*gap_c를 해주어야 범위 안에서 바뀝니다.  
                    mat2[b-len*gap_r+len*cnt][r-1-a + len*gap_c] = mat[a][b];
                }
            }
            gap_c++;
            gap_r++;
        }
        cnt++;
        gap_r=0;
        gap_c=0;
 
    }
    memcpy(mat, mat2, sizeof(mat2));
}
 
void work_4(int len){
    int r, c;
    int gap_c=0, gap_r=0;
    int cnt=0;
    
    for(int i=0; i<range; i+=len){
        for(int j=0; j<range; j+=len){
            r = i + len;
            c = j + len;
            for(int a=i; a<r; a++){
                for(int b=j; b<c; b++){
                    mat2[c-1-b + len*gap_r][a + len*gap_c - len*cnt] = mat[a][b];
                }
            }
            gap_c++;
        }
        cnt++;
        gap_r++;
        gap_c=0;
    }
    memcpy(mat, mat2, sizeof(mat2));
}
 
void work_5(int len){
    // 전체를 상하반전시키고  
    work_1(range);
    // l단계에서 부분을 상하반전시키면, 부분을 유지한 채로 전체 상하반전이 가능하다. 
    work_1(len);
}
 
void work_6(int len){
    // work_5와 같은 설명  
    work_2(range);
    work_2(len);
}
 
void work_7(int len){
    // 전체를 시계방향으로 90도 돌리고 
    work_3(range);
    // l단계에서 부분을 반시계 방향으로 90도 돌리면, 전체를 90도 시계방향으로 돌리면서
    // 부분을 유지하는 것이 가능하다. 
    work_4(len);
}
 
void work_8(int len){
    // work_8과 같은설명  
    work_4(range);
    work_3(len);
}
 
 
void solution(){
    
    int c, len;
    
    for(int t=0; t<cmd.size(); t++){
        c = cmd[t].first;
        len = (1 << cmd[t].second);
        // l이 0이면 할 필요가 없다. 
        if(len==0) continue;
        
        if(c==1) work_1(len);
        else if(c==2) work_2(len);
        else if(c==3) work_3(len);
        else if(c==4) work_4(len);
        else if(c==5) work_5(len);
        else if(c==6) work_6(len);
        else if(c==7) work_7(len);
        else if(c==8) work_8(len);
    }
    print();
 
}
 
 
int main(void){
    
    cin >> n >> r;
    
    range = 1 << n;
    int num;
    for(int i=0; i<range; i++){
        for(int j=0; j<range; j++){
            cin >> num;
            mat[i][j] = num;
        }
    }    
    
    int k, l;
    for(int i=0; i<r; i++){
        cin >> k >> l;
        cmd.push_back({k, l});
    }
    
    solution();
}

 

 

 

시행착오

    - 부분을 나누어서 반전, 회전을 시켜주어야해서 idx처리가 까다로웠다. 아무래도 깔끔하게 정리하는 방법이 있는 듯하다. 나중에 수정해서 시도해 봐야겠다.