[ 알고리즘 - 1 ] 2차원 배열(M X M) 90도 회전하기

안녕하세요. 

오늘은 2차원 배열을 90도로 회전하는 알고리즘을 고민해볼 예정입니다.

 

우선 바로 좋은 방법이 떠오르지 않아서.. 예시를 통해 규칙을 찾아보려고 합니다.

먼저, 다음과 같이 2차원 배열이 있다고 가정하겠습니다.

 

<2차원 배열 예시>

0,0	0,1	0,2	0,3
1,0	1,1	1,2	1,3
2,0	2,1	2,2	2,3
3,0	3,1	3,2	3,3

 

앞에 숫자는 행을 나타내고 뒤에 숫자는 열을 나타냅니다.

(ex. [0][1], [2][3] ...)

 

저 상태에서 시계방향으로 90도 회전한다고 했을 때 [0][0] 부터 [3][3] 까지 이동 되는 경로는 아래와 같습니다.

 

[0][0] -> [0][3]

[0][1] -> [1][3]

[0][2] -> [2][3]

[0][3] -> [3][3]

 

[1][0] -> [0][2]

[1][1] -> [1][2]

[1][2] -> [2][2]

[1][3] -> [3][2]

 

[2][0] -> [0][1]

[2][1] -> [1][1]

[2][2] -> [2][1]

[2][3] -> [3][1]

 

[3][0] -> [0][0]

[3][1] -> [1][0]

[3][2] -> [2][0]

[3][3] -> [3][0]

 

이제 규칙이 조금 눈에 들어오는 것 같습니다.

제 눈에 보인 규칙은 다음과 같습니다.

 

※ 이동되기 전 행의 열은 이동된 후의 행이 된다.

※ 이동되기 전 행은 이동된 후의 열에 "2차원 배열의 최대 인덱스 - 이동되기 전 행의 인덱스"이 된다.

 

이 두가지 규칙을 통해 2차원 배열을 90도로 시계방향으로 회전하는 함수를 다음과 같이 작성해보았습니다.

 

function rotateBox(box) {
  var box_max_index = box.length - 1;

  var new_box = [];
  for (var i = 0; i < box.length; i++) {
    var row = [];
    for (var k = 0; k < box.length; k++) {
      row.push(0);
    }
    new_box.push(row);
  }

  for (var i = 0; i < box.length; i++) {
    for (var k = 0; k < box[i].length; k++) {
      var after_row = k;
      var after_col = box_max_index - i;
      new_box[after_row][after_col] = box[i][k];
    }
  }

  return new_box;
}

 

다음과 같이 테스트를 진행해보았습니다.

테스트 케이스 1

테스트 케이스 2

 

테스트 케이스 2가지로 테스트 해봤을 때 이상없이 잘 나오는 것을 확인하였습니다.

 

시계 방향으로 90도로 회전하는 것은 구현했는데 그럼 반시계 방향으로 90도 회전하는 것은 어떻게 하면 좋을까요? 물론 지금 구현한 rotateBox 함수를 3번 호출하면 반시계 방향으로 90도 회전한 것과 같은 결과가 나오긴 하겠지만 ㅎㅎ.. 반시계 방향으로 90도 돌렸을 때는 어떤 규칙이 나오는지 한번 확인해보겠습니다.

 

[0][0] -> [3][0]

[0][1] -> [2][0]

[0][2] -> [1][0]

[0][3] -> [0][0]

 

[1][0] -> [3][1]

[1][1] -> [2][1]

[1][2] -> [1][1]

[1][3] -> [0][1]

 

[2][0] -> [3][2]

[2][1] -> [2][2]

[2][2] -> [1][2]

[2][3] -> [0][2]

 

[3][0] -> [3][3]

[3][1] -> [2][3]

[3][2] -> [1][3]

[3][3] -> [0][3]

 

반시계 방향으로 90도 돌렸을 때도 규칙이 눈에 들어오는 것 같습니다.

제 눈에 보인 규칙은 다음과 같습니다.

 

※ 이동되기 전 행의 열은 이동된 후의 "2차원 배열의 최대 인덱스 - 이동되기 전 행의 열의 인덱스" 행이 된다.

※ 이동되기 전 행은 이동된 후의 행의 열이 된다.

 

위 규칙을 토대로 조금 전 작성했던 rotateBox 함수를 다음과 같이 수정해보았습니다.

 

function rotateBox(box, direction) {
  // direction 이 1이면 반시계방향 처리, 그 외라면 시계방향 처리
  var box_max_index = box.length - 1;

  var new_box = [];
  for (var i = 0; i < box.length; i++) {
    var row = [];
    for (var k = 0; k < box.length; k++) {
      row.push(0);
    }
    new_box.push(row);
  }

  for (var i = 0; i < box.length; i++) {
    for (var k = 0; k < box[i].length; k++) {
      // 디폴트로 시계방향 처리
      var after_row = k;
      var after_col = box_max_index - i;

      if (direction === 1) {
        // 반시계방향이면
        after_row = box_max_index - k;
        after_col = i; 
      }

      new_box[after_row][after_col] = box[i][k];
    }
  }

  return new_box;
}

 

다음과 같이 테스트를 진행하였습니다.

 

테스트 케이스 1

테스트 케이스 2

테스트 케이스 2가지로 테스트 해봤을 때 이상없이 잘 나오는 것을 확인하였습니다.

 

이렇게 2차원 배열을 90도로 회전하는 함수를 작성해보았습니다.

 

봐주셔서 감사합니다. :)