C++で行列を螺旋状に出力する方法（スパイラルマトリックス）

スパイラルマトリックスとは

行列（マトリックス）の要素を螺旋状に出力する問題を考えてみましょう。まず最初の行全体を左から右へ出力し、次に最終列を上から下へ、続いて最終行を右から左へ、さらに最初の列を下から上へと出力します。この一連の流れを内側へ向かって繰り返すことで、行列の要素を螺旋状に表示できます。

例として、次のような3行6列の行列を用意しました。

この行列を螺旋状に出力すると、結果は次のようになります。

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

アルゴリズムの手順

この問題は、以下の手順で解くことができます。

• 現在の行を表す currRow と現在の列を表す currCol を 0 で初期化する

• currRow と currCol が行列の範囲内である間、以下を繰り返す

  • 上端の行を左から右へ出力する（currCol から n-1 まで）

  • currRow を 1 増やして次の行へ移動する

  • 右端の列を上から下へ出力する（currRow から m-1 まで）

  • n を 1 減らし、新しい右端の列を設定する

  • currRow が m 未満の場合、下端の行を右から左へ出力し、m を 1 減らす

  • currCol が n 未満の場合、左端の列を下から上へ出力し、currCol を 1 増やす

このように、出力済みの外周を順に「削り落として」いくことで、範囲を内側へ狭めながら螺旋状の走査を実現しています。

C++による実装例

それでは、実際の実装を見てみましょう。コードのコメントも併せて確認すると、処理の流れがつかみやすくなります。

#include <iostream>
#define ROW 3
#define COL 6
using namespace std;
int array[ROW][COL] = {{1, 2, 3, 4, 5, 6},
    {7, 8, 9, 10, 11, 12},
    {13, 14, 15, 16, 17, 18}};
void dispSpiral(int m, int n){
    int i, currRow = 0, currCol = 0;
    while (currRow < ROW && currCol < COL){
        for (i = currCol; i < n; i++){ //最初の行を左から右へ出力
        cout << array[currRow][i]<<" ";
    }
    currRow++; //次の行へ移動
    for (i = currRow; i < m; ++i){ //最終列を上から下へ出力
        cout << array[i][n-1]<<" ";
    }
    n--; //n-1列目を新しい最終列として設定
    if ( currRow < m){ //currRowが範囲内の場合、最終行を出力
        for (i = n-1; i >= currCol; --i){
            cout << array[m-1][i]<<" ";
        }
        m--; //行の範囲を狭める
    }
    if (currCol < n){ //currColが範囲内の場合、最初の列を出力
        for (i = m-1; i >= currRow; --i){
            cout << array[i][currCol]<<" ";
        }
        currCol++;
        }
    }
}
int main(){
    dispSpiral(ROW, COL);
}

入力

[[1,2,3,4,5,6]
[7,8,9,10,11,12]
[13,14,15,16,17,18]]

出力

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

このアルゴリズムの計算量は O(m×n) で、行列の全要素をちょうど1回ずつ訪問するため、非常に効率的です。正方行列だけでなく、行数と列数が異なる長方形の行列にも対応できる点もポイントです。