개발 블로그

문제 링크 : www.acmicpc.net/problem/16927

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 10^9
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

접근 방법

nanyoungkim.tistory.com/78

문제와 동일한데, 조건 하나가 다르다. R의 범위가 1000에서 10^9 까지 늘어났다는 것이다. 

예를 들어보자.

여기서 map[0][0]이 1번 전진하면 map[1][0]으로 간다. 그런데 1번 전진이 아니라 13번, 25번 전진해도 map[1][0]으로 간다. 

즉,

1 mod 12

13 mod 12

25 mod 12

는 모두 1임을 알 수 있는데, 여기서 modulus 12는 가장 바깥쪽 박스의 칸 수가 된다. 이는 2*N + 2*M -4 로 구할 수 있다. (-4는 각 모서리의 수들이 반복돼서 더해준 것을 뺀 것이다.)

박스가 하나씩 안 쪽으로 들어갈 때마다 가로, 세로의 길이는 각각 2씩 감소하는 것을 알 수 있다.

배열 돌리기 1번에서는 "각 박스에 대해 1칸 전진" 을 R번 반복 했다면, 

배열 돌리기 2번에서는 "박스 한개에 대해 R번 전진" 을 박스 개수만큼 반복해줬다.

결론은 박스 개수만큼 반복하는데, 한 박스마다 회전할 수를 R이 아닌 "R mod 박스칸수" 로 지정해서 R이 10^9처럼 큰 수가 들어와도 효율적으로 돌아갈 수 있게 했다.

//21.03.10
//next가 배열 범위 넘어가면 dr[],dc[]의 인덱스 증가
//top, right, bottom, left 순서로 칸 이동시킴
//(시계 반대방향으로 전진해야하므로 dr,dc의 인덱스는 오,아,왼,위 순서)

#include <iostream>
#include <algorithm>


using namespace std;

int map[301][301];
int N,M,R;

//오, 아, 왼, 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void rotate(int start, int len){
    
    int r = R%len;			//len은 박스의 총 칸 수
    for(int i = 0; i<r; i++){   //r칸 전진
        
        int startVal = map[start][start];
        int r = start;
        int c = start;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==start && nc==start) break;
            if(start<=nr && nr<N-start && start<=nc && nc<M-start){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[start+1][start] = startVal; //처음에 시작지점 빼놨던거 마지막에 빈 자리에 넣어줌.
        
    }

    
}


int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    
    int cnt = min(N,M)/2;       //  박스 수


    int n=N, m=M;
    
    for(int i = 0; i<cnt; i++){ //반복문 1번에,  박스 1개가 R만큼 전진함
            //시작 지점
        rotate(i, 2*n + 2*m -4);
        n-=2;	//박스 안으로 들어갈때마다 가로,세로 2씩 줄어듦.
        m-=2;
        
    }
    
    
    
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}