【ITニュース解説】Day 4 of 100 days dsa coding challenge

「100日間DSAコーディングチャレンジ」とは、データ構造（Data Structures）とアルゴリズム（Algorithms）に関する問題を、100日間にわたって毎日継続して解くことで、プログラミングスキルを向上させるための取り組みである。このチャレンジの目的は、問題解決能力を研ぎ澄まし、コーディング技術を高め、日々新しいことを学ぶことにある。GeeksforGeeksというプログラミング学習プラットフォームが提供する「Problem of the Day (POTD)」という、毎日出題される問題に挑戦することで、これらのスキルを実践的に磨き上げていく。

今回取り組んだ問題は「Rat in a Maze」というもので、難易度はMedium、正答率は約35.75%と示されている。この問題は、N×Nの正方行列で表現された迷路の中にネズミがおり、ネズミは左上のセル(0,0)からスタートして右下のセル(N-1, N-1)に到達することを目指す。迷路の各セルは2つの値のいずれかを持つ。値が0のセルはブロックされておりネズミは通過できないが、値が1のセルは自由に通ることができる。ネズミは現在の位置から上下左右の4方向に移動可能である。しかし、いくつかの重要な制約がある。ネズミは迷路の境界外には移動できず、一度通ったセルは、同じ経路の途中では再訪できない。つまり、あるパスを探索中に同じ場所を二度通ることは許されないが、別の異なるパスを探索する際には、以前通った場所を再び通ることは可能である。最終的なタスクは、ネズミがスタート地点からゴール地点まで到達できる全ての可能な経路を見つけ出し、それらを文字列（例: 'D'は下、'U'は上、'L'は左、'R'は右）として表現し、最終的に辞書順（アルファベット順）にソートしたリストとして返すことである。もし経路が一つも存在しない場合は、空のリストを返さなければならない。迷路のサイズNは2から5の間と比較的小さい。

このような迷路探索問題の解決策として、一般的に「深さ優先探索（DFS: Depth-First Search）」と呼ばれるアルゴリズムが非常に適している。深さ優先探索は、ある地点から行ける場所を一つ選び、そこからさらに深く、可能な限り遠くまで探索を進めていく方法である。もし行き止まりにぶつかったり、目的地に到達したりした場合、一つ前の地点に戻り、そこからまだ試していない別の経路を探索し直す。この「一つ戻る」動作を「バックトラック」と呼ぶ。

コードでは、まずSolutionクラス内のratInMazeメソッドが迷路を表す2次元リストmazeを受け取る。 最初に、迷路のサイズnを取得し、結果として経路を格納する空のリストresを準備する。 重要な初期チェックとして、もしスタート地点であるmaze[0][0]が0（ブロックされている）であったり、ゴール地点であるmaze[n-1][n-1]が0（ブロックされている）であったりする場合、ネズミはスタートもゴールもできないため、経路は存在しない。この場合はすぐに空のリストresを返して処理を終了する。

次に、visという名前の2次元リストを作成し、すべての要素を0で初期化する。このvisは「訪問済みマップ」として機能し、ネズミが探索中にどのセルを訪問したかを記録するために使用される。0は未訪問、1は訪問済みを表す。 そして、深さ優先探索の主要なロジックを実装するためにdfsというヘルパー関数が定義される。このdfs関数は、現在のネズミの位置を示す行インデックスiと列インデックスj、そして現在までの移動経路を表す文字列pathの3つの引数を受け取る。

dfs関数内にはまず「ベースケース」、つまり探索が終了する条件が書かれている。もし現在の位置(i, j)がゴール地点の(n-1, n-1)に到達した場合、有効な経路が見つかったことを意味するため、現在の経路文字列pathをresリストに追加し、dfs関数の呼び出しを終了する。

次に「再帰ステップ」として、ネズミが現在の位置からどのように移動するかを記述する。 まず、現在のセル(i, j)にネズミがいることを示すために、vis[i][j]を1に設定し、このセルを訪問済みとする。 その後、ネズミが移動できる四方向（下、左、右、上）それぞれについて、移動が可能かどうかをチェックする。コードの記述順序は、下、左、右、上の順となっている。 例えば、下方向への移動を試みる場合、if i+1 < n and not vis[i+1][j] and maze[i+1][j]:という条件が評価される。

• i+1 < n：下方向への移動が迷路の範囲内であるか（行インデックスが迷路のサイズを超えていないか）。
• not vis[i+1][j]：移動先のセル(i+1, j)がまだ訪問されていないか。visが1であれば既に訪問済みであり、not visはvisが0であることを意味する。
• maze[i+1][j]：移動先のセルがブロックされていないか（値が1であるか）。

これらすべての条件を満たす場合、ネズミは下方向へ移動できる。そこで、dfs(i+1, j, path+'D')というようにdfs関数を再帰的に呼び出す。この際、iはi+1に更新され、pathには下方向への移動を示す文字'D'が追加される。 他の三方向（左、右、上）についても同様の条件チェックと再帰呼び出しを行う。それぞれの移動方向に対応する文字（'L'、'R'、'U'）がpathに追加される。

全ての方向への探索が終わり、dfs関数が現在の位置から呼び出された全ての再帰呼び出しから戻ってきたら、非常に重要な「バックトラック」処理を行う。それは、vis[i][j] = 0と現在のセルを未訪問の状態に戻すことである。なぜこの処理が必要なのかというと、ネズミが迷路を進む際に、ある経路で既に通ったセルを、別の経路を探索する際に再び通ることを可能にするためである。これにより、「同じパスでは再訪しない」という条件を満たしつつ、迷路のすべての可能な経路を探索できる。

dfs関数が定義された後、最初の呼び出しはdfs(0, 0, '')として行われる。これは、ネズミがスタート地点(0, 0)から、まだ何も移動していない空のパス''で探索を開始することを意味する。 すべての探索が完了し、dfsの最初の呼び出しが戻ってきたら、resリストには見つかったすべての経路文字列が格納されている。最後に、このresリストをsorted(res)によって辞書順にソートし、最終結果として返す。

この「Rat in a Maze」問題を通じて、システムエンジニアを目指す初心者は、深さ優先探索とバックトラックという強力なアルゴリズムの概念を学ぶことができる。また、迷路のようなグリッド上での探索問題の解き方、再訪禁止といった制約を「訪問済みマップ」で管理する方法、そして再帰関数の効果的な使い方など、実践的なプログラミングスキルを身につけることが可能である。このようなコーディングチャレンジに継続して取り組むことは、複雑な問題を論理的に分解し、アルゴリズムを設計し、それをコードとして実装する能力を向上させる上で非常に有益である。