C++で余分な領域を使用せずに行列を90度回転する方法

2次元配列から形成される行列が与えられ、それを追加のメモリ領域（extra space）を一切使わずに90度回転させることが課題です。ここでは時計回りの回転を扱い、回転後には最初の行が最後の列へ、2番目の行が後ろから2番目の列へ、というように行と列が入れ替わります。この問題の難しい点は、補助配列を作らず、元の配列の中だけで要素を入れ替える「インプレース処理」で完結させることにあります。

入出力のシナリオ

入力 −

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

出力 −

追加の領域を使用せずに行列を90度（時計回り）回転した結果：
2 9  5
8 16 1
9 12 4

説明 − 整数型の2次元配列が与えられており、これを時計回りに90度回転させます。

回転前：
{ { 5, 1, 4},
{ 9, 16, 12 },
{ 2, 8, 9}}
回転後：
2 9  5
8 16 1
9 12 4

入力 −

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

説明 − 整数型の2次元配列が与えられており、これを時計回りに90度回転させます。

回転前：
{ { 2, 1, 9},
{ 11, 6, 32 },
{ 3, 7, 5}}
回転後：
3 11 2
7 6  1
5 32 9

プログラムで使用するアプローチ

1. 素朴なアプローチ（Naive Approach）

• row_col_size × 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」という順に、4つの要素を循環的に入れ替えます。
• 最後に、i を 0 から row_col_size 未満まで、内側で j を 0 から row_col_size 未満まで進める二重ループによって arr[i][j] を出力します。

2. 効率的なアプローチ（Efficient Approach）

• 同様に2次元整数配列を受け取り、Rotate_ClockWise(arr) に渡します。
• 関数内部では、次の2段階の処理で回転を実現します。
  • まず副対角線を軸とした入れ替えを行います：i を 0 から row_col_size 未満まで、j を 0 から row_col_size − i 未満までループし、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] を交換します。
• 最後に、二重ループで結果の行列を出力します。

どちらのアプローチも時間計算量は O(n²)、追加で必要な領域は一時変数のみの O(1) です。素朴なアプローチが各サイクルの4要素を直接入れ替えるのに対し、効率的なアプローチは「斜め方向の入れ替え＋行の反転」という2段階構成になっている点が違いです。

素朴なアプローチのコード例

#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