Matrix - tanakakenji/Rinko GitHub Wiki

Introduction（イントロダクション）

行列（Matrix）とは2次元の配列のことです。行列に関する問題は、通常ダイナミックプログラミングやグラフ探索に関連して出題されます。

行列は、各セルをグラフ上のノードとして扱い、上下左右で隣接するセルとのつながりを表すことで、グラフの形で表すことができます（端や角のセルは隣接数が4より少ない）。ここでは、グラフとして行列を使わない問題について扱います。グラフとして行列を使うことが想定される問題は、グラフセクションを参照してください。

Corner cases（コーナーケース）

空の行列
- 配列の長さが0でないか確認しましょう。
1 x 1 の行列
1行または1列しかない行列

Techniques（テクニック）

N x M の空の行列を作成する

探索やダイナミックプログラミングに関連する問題では、訪問状態やDPテーブルを保持するために、同じ大きさ・次元の空の行列を複製して使うことがほとんどです。使用するプログラミング言語で、このような処理に慣れておきましょう。

Pythonでは、以下のように1行で簡単に実行できます。

# 行列が空ではないと仮定
zero_matrix = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]

行列のコピー（Python）

copied_matrix = [row[:] for row in matrix]

行列の転置

行列の転置（Transpose）は、行と列を入れ替えて得られる行列のことです。

マス目を使った多くのゲーム（例: 三目並べ、数独、クロスワード、Connect 4、Battleshipなど）は、行列の形でモデル化できます。ゲームの勝敗判定を行う際には、縦と横の両方向で判定が必要になることがよくあります。例えば、三目並べやConnect 4、クロスワードなどでは、まず行（横方向）のチェック処理を実装し、次に行列を転置してから同じロジックを使えば、縦方向（転置後は横方向となる）のチェックも簡単に実装できます。

Pythonでの転置は非常に簡単で、以下のように書けます。

transposed_matrix = zip(*matrix)

Essential questions（重要な問題）

このトピック（行列）を学習する際、まず練習しておくべき重要問題はこちらです。

Set Matrix Zeroes
Spiral Matrix