JavaScriptの再帰で解く！行列を螺旋状に巡回するスパイラルトラバーサル問題

問題の概要

まず、次のような2次元配列を考えてみましょう。

const arr = [
    [1, 2, 3, 4],
    [12,13,14,5],
    [11,16,15,6],
    [10,9, 8, 7]
];

この配列は正方行列(行数と列数が等しいマトリックス)であることが前提となっています。

私たちの課題は、この配列を受け取り、外側から内側へ渦巻き状に要素を取り出して新しい配列を構築するJavaScript関数を書くことです。カタツムリが這い残した跡(スネイルトレイル)のように、マトリックスの外周をぐるりと一周しながら、徐々に中心へ収束していきます。

したがって、上記の配列に対する期待される出力は次のようになります。

const output = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];

アプローチ：再帰を使う

この問題は再帰(リカージョン)を使うことで、シンプルかつエレガントに解くことができます。基本的な考え方は以下の通りです。

• マトリックスの最上行を取り出し、結果の配列に連結する
• 残りのマトリックスを反時計回りに90度回転させる
• マトリックスの行数が1になるまで、この操作を繰り返す

「上の一行を剥がして、残りを回転する」という操作を繰り返すだけで、自然に螺旋順の並びが得られるのがポイントです。

コード例

実際のコードは次のようになります。

const arr = [
    [1, 2, 3, 4],
    [12,13,14,5],
    [11,16,15,6],
    [10,9, 8, 7]
];
const spiralForm = arr => {
    return arr.length > 1 ?
    arr.splice(0,1)[0]
    .concat(spiralForm(arr[0].map((c, i) => {
        return arr.map(r => r[i]);
    })
    .reverse())) :
    arr[0]
}
console.log(spiralForm(arr));

出力

このコードを実行すると、コンソールには次のように出力されます。

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

コードの仕組みを分解してみる

1. ベースケース(終了条件)： arr.length が1以下になったら、残りの arr[0](最後の行や中央の要素)をそのまま返します。ここで再帰が停止します。
2. 最上行の取り出し： splice(0, 1)[0] によって先頭の行を取り出します。これが螺旋の一段目に相当します。
3. 90度回転： 残りの配列に対して map() で各列を抽出し、reverse() で列の順序を反転することで、マトリックス全体を反時計回りに90度回転させます。これにより「右端の列」が新しい「最上行」になります。
4. 連結と再帰呼び出し： 取り出した行と、回転後のマトリックスに対する再帰呼び出しの結果を concat() でつなぎ合わせて返します。

最初のステップでは [1, 2, 3, 4] が取り出され、残りの3×4マトリックスが回転されて [5, 6, 7] が次の最上位の行になります。以降も同様に 8、9、10…と外周から順に要素が剥がれていき、最終的に完全な螺旋順の1次元配列が完成します。

注意点：splice() の副作用

この実装では splice() を使用しているため、引数として渡された元の配列が破壊的に変更される点に注意が必要です。元の配列を後続の処理でも使いたい場合は、あらかじめ [...arr] や arr.map(row => [...row]) などでコピーを作成してから関数に渡すようにしましょう。