C++で2次元行列を反時計回りのスパイラル形式で出力する方法

この記事では、2次元行列が与えられたときに、そのすべての要素を反時計回りのスパイラル形式で出力する方法を解説します。

反時計回りのスパイラル形式とは？

反時計回りのスパイラル形式とは、行列の左上の要素から開始し、最初に下方向へ進み、続いて右→上→左と方向を変えながら、渦巻き状に外側から内側へと要素をたどっていく走査方法です。

例として、次の4×4の行列を見てみましょう。

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

この行列を反時計回りに走査すると、出力は「1 5 9 13 14 15 16 12 8 4 3 2 6 10 11 7」となります。

入力例と出力例

Input:
    2 4 6
    1 7 9
    5 0 3
Output: 2 1 5 0 3 9 7

解法のアプローチ

この問題は、4つのループを使うことで効率的に解くことができます。それぞれのループが1つの方向（下・右・上・左）を担当し、一巡するごとに走査対象の境界を内側へ狭めていきます。

具体的な流れは以下の通りです。

1. 左端の列を上から下へ走査する
2. 最下行を左から右へ走査する
3. 右端の列を下から上へ走査する
4. 最上行を右から左へ走査する
5. 境界を更新し、未出力の要素があれば次の内側の層へ進む

すでに出力した要素数をカウントしておき、全要素数（行数×列数）に達した時点で処理を終了することで、同じ要素を二重に出力するのを防ぎます。

C++での実装例

以下は、上記のアルゴリズムを実装したC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
#define R 3
#define C 3
void printCounterClockwiseSpiral(int m, int n, int matrix[R][C]){
    int i, k = 0, l = 0;
    int count = 0;
    int total = m * n;
    while (k < m && l < n){
        if (count == total)
            break;
        // 左端の列を上から下へ
        for (i = k; i < m; ++i){
            cout<<matrix[i][l]<<" ";
            count++;
        }
        l++;
        if (count == total)
            break;
        // 最下行を左から右へ
        for (i = l; i < n; ++i){
            cout<<matrix[m - 1][i]<<" ";
            count++;
        }
        m--;
        if (count == total)
            break;
        // 右端の列を下から上へ
        if (k < m){
            for (i = m - 1; i >= k; --i){
                cout<<matrix[i][n - 1]<<" ";
                count++;
            }
            n--;
        }
        if (count == total)
            break;
        // 最上行を右から左へ
        if (l < n){
            for (i = n - 1; i >= l; --i){
                cout<<matrix[k][i]<<" ";
                count++;
            }
            k++;
        }
    }
}
int main() {
    int mat[R][C] = {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9}
    };
    cout<<"Counter Clockwise Spiral form of the matrix is :\n";
    printCounterClockwiseSpiral(R, C, mat);
    return 0;
}

ここで、変数 k と l は未走査領域の開始行・開始列を、m と n は終了行・終了列を表しています。各方向の走査が完了するたびにこれらの値を更新することで、走査範囲が渦巻き状に内側へと縮んでいきます。

出力結果

上記プログラムを実行すると、次の出力が得られます。

Counter Clockwise Spiral form of the matrix is :
1 4 7 8 9 6 3 2 5

まとめ

行列のスパイラル走査は、境界変数を適切に管理しながら4方向のループを回すことで実現できます。反時計回りの場合は、一般的な時計回りとは異なり最初に下方向へ進む点に注意しましょう。すべての要素を一度ずつ訪れるため、計算量は O(m×n) となります。