배열 돌리기 1 (백준 16926)

문제

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

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

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

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전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

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

예제 출력 1

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

예제 입력 2

5 4 7
1 2 3 4
7 8 9 10
13 14 15 16
19 20 21 22
25 26 27 28

예제 출력 2

28 27 26 25
22 9 15 19
16 8 21 13
10 14 20 7
4 3 2 1

예제 입력 3

2 2 3
1 1
1 1

예제 출력 3

1 1
1 1

---

🚀문제 해석

예시에서 알 수 있듯이 r번 회전할 때마다 Math.min(N, M) / 2 개의 사각형을 회전시켜야한다.

간단히 수도코드를 작성하면 다음과 같다.

 

회전시킬 때 주의할 점은 어떤 곳을 목표지점으로 회전할 것인지 결정하는 것이다.

rectCount = Math.min(N, M) / 2 // 회전해야하는 사각형의 갯수

for cnt = 0, cnt < rectCount, cnt++ {
    row = n - cnt - 1 // 세로의 끝
    col = m - cnt - 1 // 가로의 끝
    tmp = maps[cnt][cnt] // 회전하는 사각형의 기준점
    
    // 위에 회전시키기 (오른쪽에서 왼쪽방향으로)
    for j = cnt, j < col, j++
    maps[cnt][j] = maps[cnt][j+1]
    
    // 오른쪽 회전시키기 (아래에서 위쪽 방향으로)
    for i = cnt, i < row, i++
    maps[i][col] = maps[i+1][col]
    
    // 아래 회전시키기 (왼쪽에서 오른쪽방향으로)
    for j = col, j > cnt, j--
    maps[row][j] = maps[row][j-1]
    
    // 왼쪽 회전시키기 (아래에서 위쪽방향으로)
    for i = col, i > cnt, i--
    maps[i][cnt] = maps[i-1][cnt]
    
    maps[cnt+1][cnt] = tmp
}

 

🛠코드

let [a, ...maps] = require('fs').readFileSync(0).toString().trim().split('\n');

let [n, m, r] = a.split(' ').map(Number);

maps = maps.map(elem => elem.split(' ').map(Number));

function rotate(n, m, maps) {

   // 몇개의 사각형을 회전시킬 지를 정한다.

   const rectCount = Math.min(n, m) / 2;

   for (let cnt = 0; cnt < rectCount; cnt++) {

      const row = n - cnt - 1;

      const col = m - cnt - 1;

      // 회전해야하는 사각형의 기준점

      const tmp = maps[cnt][cnt];

      // 위 : 오른쪽에서 왼쪽으로

      for (let j = cnt; j < col; j++) {

         maps[cnt][j] = maps[cnt][j + 1];

      }

      // 오른쪽 : 아래에서 위로

      for (let i = cnt; i < row; i++) {

         maps[i][col] = maps[i + 1][col];

      }

      // 아래 : 왼쪽에서 오른쪽으로

      for (let j = col; j > cnt; j--) {

         maps[row][j] = maps[row][j - 1];

      }

      // 왼쪽 : 위에서 아래로

      for (let i = row; i > cnt; i--) {

         maps[i][cnt] = maps[i - 1][cnt];

      }

      maps[cnt + 1][cnt] = tmp;

   }

}

function solution(n, m, r, maps) {

   for (let i = 0; i < r; i++) {

      rotate(n, m, maps);

   }

   maps.map(row => console.log(row.join(' ')));

}

solution(n, m, r, maps);

 

배열을 회전하는 문제가 자주 나오는 거 같다. 이 문제 역시 백준 17144 문제랑 매우 유사하다.

그 문제도 회전할 때 목표지점을 지정하지 않아서 구현할 때 매우 애를 먹었다.

어떤 지점을 향해 회전할 것인지 명확하게 정하자.