C++에서 추가 공간 없이 행렬을 90도 회전하는 방법

2차원 배열로 구성된 정방행렬(N×N)이 주어졌을 때, 이를 시계 방향으로 90도 회전하는 것이 목표입니다. 회전이 완료되면 첫 번째 행은 마지막 열로, 두 번째 행은 가운데 열로 이동하는 형태가 됩니다. 여기서 핵심 조건은 어떠한 추가 공간(보조 배열)도 사용하지 않고 원본 배열 자체에서(in-place) 연산을 수행해야 한다는 점입니다.

입출력 예시

입력

int arr[row_col_size][row_col_size] = { { 5, 1, 4},
    { 9, 16, 12 },
    { 2, 8, 9}}

출력

추가 공간 없이 행렬을 90도 회전한 결과:
4 12 9
1 16 8
5 9  2

설명 — 정수형 2차원 배열이 주어졌으며, 이를 시계 방향으로 90도 회전합니다.

회전 전:
{ { 5, 1, 4},
{ 9, 16, 12 },
{ 2, 8, 9}}
회전 후:
4 12 9
1 16 8
5 9  2

다른 예시도 살펴보겠습니다.

입력

int arr[row_col_size][row_col_size] = { { 2, 1, 9},
    { 11, 6, 32 },
    { 3, 7, 5}}

출력

추가 공간 없이 행렬을 90도 회전한 결과:
3 11 2
7 6  1
5 32 9

프로그램에 적용된 접근 방식

1. 단순 접근법 (Naive Approach)

행렬의 바깥층부터 안쪽층까지 한 겹씩 진행하면서, 해당 층을 이루는 네 개의 요소를 임시 변수 하나만으로 순환 교환(swap)하는 방식입니다.

• row_col_size 크기의 정수형 2차원 배열을 입력받아 하나의 행렬로 취급합니다.

• 배열 데이터를 Rotate_ClockWise(arr) 함수에 전달합니다.

• Rotate_ClockWise(arr) 함수 내부 동작은 다음과 같습니다.

  • i를 0부터 row_col_size / 2 미만까지 반복하는 FOR 루프를 시작합니다.

  • 루프 내부에서 j를 i부터 row_col_size - i - 1 미만까지 반복하는 FOR 루프를 시작합니다.

  • 루프 내부에서 ptr에 arr[i][j]를 저장하고, arr[i][j] ← arr[row_col_size - 1 - j][i], arr[row_col_size - 1 - j][i] ← arr[row_col_size - 1 - i][row_col_size - 1 - j], arr[row_col_size - 1 - i][row_col_size - 1 - j] ← arr[j][row_col_size - 1 - i], arr[j][row_col_size - 1 - i] ← ptr 순서로 값을 교환하여 네 개의 요소를 한 사이클로 회전시킵니다.

• 마지막으로 i를 0부터 row_col_size 미만까지, j를 0부터 row_col_size 미만까지 반복하며 arr[i][j]를 출력합니다.

2. 효율적인 접근법 (Efficient Approach)

행렬의 대각선을 기준으로 전치(transpose)를 수행한 뒤, 각 행을 좌우로 뒤집으면 시계 방향 90도 회전과 동일한 결과를 얻을 수 있습니다.

• row_col_size 크기의 정수형 2차원 배열을 입력받아 하나의 행렬로 취급합니다.

• 배열 데이터를 Rotate_ClockWise(arr) 함수에 전달합니다.

• Rotate_ClockWise(arr) 함수 내부 동작은 다음과 같습니다.

  • i를 0부터 row_col_size 미만까지 반복하는 FOR 루프를 시작합니다.

  • 루프 내부에서 j를 0부터 row_col_size - i 미만까지 반복하는 FOR 루프를 시작합니다.

  • 루프 내부에서 ptr에 arr[i][j]를 저장하고, arr[i][j] ↔ arr[row_col_size - 1 - j][row_col_size - 1 - i]를 서로 교환하여 주대각선을 기준으로 요소를 뒤집습니다(전치).

  • 이어서 i를 0부터 row_col_size / 2 미만까지, j를 0부터 row_col_size 미만까지 반복하며 ptr에 arr[i][j]를 저장하고, arr[i][j] ↔ arr[row_col_size - 1 - i][j]를 서로 교환하여 행을 상하 반전합니다.

• 마지막으로 i를 0부터 row_col_size 미만까지, j를 0부터 row_col_size 미만까지 반복하며 arr[i][j]를 출력합니다.

단순 접근법 코드

예제

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
   for(int i = 0; i < row_col_size / 2; i++){
      for(int j = i; j < row_col_size - i - 1; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - j][i];
         arr[row_col_size - 1 - j][i] = arr[row_col_size - 1 - i][row_col_size - 1 - j];
         arr[row_col_size - 1 - i][row_col_size - 1 - j] = arr[j][row_col_size - 1 - i];
         arr[j][row_col_size - 1 - i] = ptr;
      }
   }
}
int main(){
   int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
   Rotate_ClockWise(arr);
   cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size; j++){
         cout << arr[i][j] << " ";
      }
      cout << '\n';
   }
   return 0;
}

출력

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
2 9  5
8 16 1
9 12 4

효율적인 접근법 코드

예제

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size - i; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - j][row_col_size - 1 - i];
         arr[row_col_size - 1 - j][row_col_size - 1 - i] = ptr;
      }
   }
   for(int i = 0; i < row_col_size / 2; i++){
      for(int j = 0; j < row_col_size; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - i][j];
         arr[row_col_size - 1 - i][j] = ptr;
      }
   }
}
int main(){
   int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
   Rotate_ClockWise(arr);
   cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size; j++){
         cout << arr[i][j] << " ";
      }
      cout << '\n';
   }
   return 0;
}

출력

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
2 9  5
8 16 1
9 12 4

두 방식 모두 O(1)의 추가 공간만 사용하며, 시간 복잡도는 행렬의 모든 요소를 한 번씩 처리하므로 O(N²)입니다. 특히 효율적인 접근법인 '전치 후 뒤집기' 방식은 로직이 직관적이고 버그 발생 가능성이 낮아 실무에서 더 널리 활용됩니다.