キューを用いた全件探索
上記の記事では、キューを用いて木構造データを探索するという話をしています。木構造データに限らず、複数の選択肢を網羅的に探索する際には、同様の手法が利用できます。
大雑把な考え方は、次の通りです。
(1) 処理中のデータについて、「次にやるべき処理」に複数の選択肢があり、選択によって処理後のデータが変わり、その先の処理がブランチしていく、というような状況を考えます。
(2) 処理後のそれぞれのデータを個別に用意して、それらをキューに詰め込んでおきます。
(3) キューからデータを取り出して、次の処理を行います。処理結果を再びキューに詰め込みます。
これを繰り返すことにより、複数の選択肢の組み合わせパターンをすべて網羅することができます。ただし、処理対象のデータが多い場合、(2) でデータの複製が発生するので、この部分の処理時間が長くなります。そのため、探索範囲が広い場合は、データの複製量を減らすなどの工夫が必要です。（Python のリストは参照渡しの Mutable オブジェクトなので、明示的に copy.copy / copy.deepcopy する必要がある点に注意してください。）
下記の問題は、探索範囲を制限する、データの複製を必要な場合に限定する、という両方の工夫を詰め込んだ例になります。
そもそも探索量が少ない場合
冒頭の問題は、フィールドのサイズが 16 x 16 と小さいので、すべてのデータをコピーしながら全件探索しても十分に間に合うと予想できます。公式解説 では、バックトラックが紹介されていますが、愚直にすべてのパターンを検索しても大丈夫です。つまり、次に進めるすべての方向に処理をブランチして、キューに詰め込んでいきます。
また、出発地点についてもすべてのパターンを検索する必要がありますが、すでに発見された経路に含まれる位置は、出発地点にする必要はありません。これらを実装すると下記になります。
