C++での2次元行列のジグザグ（対角）トラバーサルの実装方法

問題の概要

この記事では、2次元行列（マトリックス）のすべての要素を対角線に沿った順序、いわゆる「ジグザグ（対角）トラバーサル」で出力する方法を解説します。

まず、具体例を使って問題を理解しましょう。次のような3×3の行列が与えられたとします。

1     2     3
4     5     6
7     8     9

出力 −

1
4     2
7     5     3
8     6
9

対角トラバーサルのパターン

行列をジグザグ形式で出力する際には、どのようなパターンで要素が並ぶのでしょうか。下の図のように、要素は左下から右上へ向かう斜めのラインごとに順番に出力されます。

これが対角トラバーサルの基本的な動作です。

重要なのは、出力される行数は行列の行数と列数だけで決まるという点です。2次元行列 mat[r][c] の場合、出力は必ず r + c − 1 行になります。たとえば3×3の行列なら、3 + 3 − 1 = 5 行が出力されることになります。

C++での実装例

それでは、実際のプログラムを見てみましょう。ここでは5行4列の行列を対象に対角トラバーサルを行います。

#include <iostream>
using namespace std;
#define R 5
#define C 4
int min2(int a, int b)
{ return (a < b)? a: b; }
int min3(int a, int b, int c)
{ return min2(min2(a, b), c);}
int max(int a, int b)
{ return (a > b)? a: b; }
void printDiagonalMatrix(int matrix[][C]){
    for (int line=1; line<=(R + C -1); line++){
        int start_col = max(0, line-R);
        int count = min3(line, (C-start_col), R);
        for (int j=0; j<count; j++)
        cout<<matrix[min2(R, line)-j-1][start_col+j]<<"\t";
        cout<<endl;
    }
}
int main(){
    int M[R][C] = {{1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16},
        {17, 18, 19, 20}};
    cout<<"The matrix is : \n";
    for (int i=0; i< R; i++){
        for (int j=0; j<C; j++)
        cout<<M[i][j]<<"\t";
        cout<<endl;
    }
    cout<<"\nZigZag (diagonal) traversal of matrix is :\n";
    printDiagonalMatrix(M);
    return 0;
}

アルゴリズムのポイント

• 各対角線（ライン）は 1 から R + C − 1 まで順番に処理します。
• start_col はそのラインにおける出発列を表し、max(0, line − R) で計算します。
• 各ラインに出力される要素数は、line、(C − start_col)、R のうち最も小さい値（min3）です。
• 要素の取り出しは、行インデックスを min2(R, line) − j − 1、列インデックスを start_col + j として行います。

実行結果

The matrix is :
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
ZigZag (diagonal) traversal of matrix is :
1
5 2
9 6 3
13 10 7 4
17 14 11 8
18 15 12
19 16
20

このように、行列の要素が対角線に沿ってジグザグ状に正しく出力されていることが確認できます。時間計算量は O(R × C) であり、行列の全要素を一度ずつ訪れるため効率的な実装となっています。