개발 블로그

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

문제

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

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

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

입력

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

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

출력

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

제한

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

접근 방법

모든 박스에 대해서 시계 반대 방향으로 요소를 1칸씩 이동시키며, 이를 R번 반복한다.

여기서 박스는

이렇게 두개이다.

박스의 시작지점은 map[0][0] -> map[1][1] -> map[2][2]...... map[박스수][박스수] 이런 순으로 가게 된다.

박스의 개수는 min(N,M) / 2 개이며 문제의 조건에서 min(N,M) mod 2=0이라고 했으므로 둘 중하나는 짝수이고 (3x3) 이나 (5x5) 같은 경우는 고려하지 않아도 된다.

먼저 각 박스에 대해서 1칸 시계 반대방향으로 이동하는 걸 생각해보자.  1) map[0][0]을 시작지점으로 잡는다.

2) Top : 왼쪽으로 이동한다. 

next 칸이 now칸의 오른쪽에 있으므로 dr[],dc[]는 오른쪽.

3) Right : 위쪽으로 이동한다.

next 칸이 now칸의 아래쪽에 있으므로 dr[],dc[]는 아래.

4) Bottom : 오른쪽으로 이동한다.

next 칸이 now칸의 왼쪽 있으므로 dr[],dc[]는 왼쪽.

5) Left : 아래쪽으로 이동한다.

next 칸이 now칸의 위에 있으므로 dr[],dc[]는 위.

전체적인 로직은 위와 같으며, next 칸이 시작점으로 돌아왔을 때 반복을 멈추고, 남은 자리에 1)에서 저장했던 값을 넣어주면 된다.

//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 box){
    
    for(int i=0; i<box; i++){   //박스수만큼 반복(1칸 전진)(시작점은 start, start+1, start+2..)
        int startVal = map[i][i];       //각 박스 시작은 [0][0] -> [1][1] -> [2][2]...
        int r = i;
        int c = i;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==i && nc==i) break;
            if(i<=nr && nr<N-i && i<=nc && nc<M-i){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[i+1][i] = 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;       //  박스 수
    
    for(int i = 0; i<R; i++){       //반복문 한번에 1칸 전진하는것. 총 R칸 전진
        rotate(cnt);
    }


    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}

참고 : 4ngeunlee.tistory.com/219