[알고리즘] 2차원 배열 회전

Rotate Matrix

Problem:
Given a 2D array (matrix) of n × n elements, rotate the matrix by 90 degrees clockwise.

Example:
Input:

[
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

 

Output:

[
  [7, 4, 1],
  [8, 5, 2],
  [9, 6, 3]
]

---

 

해설

최상단에 있는 1,2,3 은 배열의 가장 끝번호로 이동한다.

 

배열로 보면 arr[0][0], arr[0][1], arr[0][2] ➡️ arr[0][끝], arr[1][끝], arr[2][끝] ... 와 같다. 

위 문장은 for 문을 통해 arr[i][j] ➡️ arr[j][N - 1 - i] 이 될 것이다. 

 

즉, 행의 값은 열로 옮겨지고, 열의 인덱스는 회전 방향에 따라 반대로 뒤집히는 구조이다.

 

왜 N - 1 - i일까?

2차원 배열을 시계 방향으로 90도 회전할 때 가장 핵심이 되는 수식은 다음과 같다.

rotateMatrix[j][N - 1 - i] = arr[i][j];

 

시계 방향으로 90도 회전한다는 건 다음과 같은 구조 변화를 의미한다.

행(row)은 열(column)로,
열은 뒤집힌 행 인덱스로 이동하게 된다. (147 ➡️ 741)

 

 

이처럼 회전을 통해

• j는 새로운 행 번호가 되고,
• i는 뒤집혀서 새로운 열 번호가 된다.

여기서 뒤집힌다는 말은,
0이 2로, 1이 1로, 2가 0으로 바뀌는 것을 말한다.

즉,
0 → 2, 1 → 1, 2 → 0
이걸 일반화한 게 바로 N - 1 - i 이다.

 

따라서 코드는 다음과 같다. 

function RotateMatrix(arr) {
  const ENDPOINT = arr.length;
  let rotateMatrix = Array.from({ length: ENDPOINT }, () => Array(ENDPOINT).fill(0)); // 2차 배열 선언

  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr[i].length; j++) {
      rotateMatrix[j][ENDPOINT - 1 - i] = arr[i][j]; // 회전 핵심 로직 (길이 - 1- i)
    }
  }

  return rotateMatrix;
}