ひとりで勝手にはじめた蟻本読書会 意外と奥が深い全探索 bit全探索 蟻本読書会の続きです。

幅優先探索と深さ優先探索

幅優先探索と深さ優先探索も全探索のひとつと考えることができます。頂点と頂点が辺でつながっている場合、つながっている辺をたどることで、すべての頂点を訪問することができる(ただしすべての頂点が直接または間接的につながっている場合のみ)のです。

幅優先探索とは?

幅優先探索ではまず出発点を決めます。そしてQueueという「最初に追加した要素を最初に取り出す」データ構造に格納します。

Queueはデータを取り出す場合、最初に格納したものが最初に取り出される構造になっています。これをFIFO (First In, First Out) といいます。

つぎにQueueからそこに格納した頂点を取り出します。最初は一番最初に格納した出発点の頂点が出てきます。その頂点からつながっている頂点を調べて、さらにQueueに格納します。

ここで注意点があります。辺が一方通行でない場合、頂点A から 頂点B に移動できる場合は、頂点B から 頂点A に移動できることを意味しています。だからといって 頂点B から移動できる頂点として A を Queue に格納してしまうと堂々巡りになってしまい、いつまで経っても処理は終わりません。そこで一度訪問した頂点にはフラグをセットして、フラグがセットされている頂点は Queue には格納しません。

この方法なら同じ頂点を何度も調べることはなくなるので、いずれある頂点から辺をとおってたどり着くことができる未訪問の頂点はなくなります。つまり出発点から直接または間接的につながっているすべての頂点を訪問することができたことになるのです。これが幅優先の全探索です。

深さ優先探索とは?

深さ優先探索でもまず出発点を決めます。そしてStackという「最後に追加した要素を最初に取り出す」データ構造に格納します。

このようなStack最初に格納したものが最後に取り出される構造をFILO(First In, Last Out、先入れ後出し)とかLIFO(Last In, First Out、後入れ先出し)とも呼ばれます。

この方法は幅優先探索でつかったQueueをStackに置き換えるだけで実装できるのですが、再帰呼び出しを使えばもっと簡略に書くことができます。

適しているのはどちらか?

では幅優先探索と深さ優先探索ではどちらが優れているのでしょうか? これはケースバイケースです。幅優先探索が適している場合もあるし、深さ優先探索が適している場合もあるし、どちらでも大差ない場合もあります。

基本的に問題をグラフ上(グラフといっても折れ線グラフや棒グラフのことではなく、頂点と頂点間の連結関係を表す辺で構成されるデータ型のこと)の探索問題に帰着できるのであれば、それは幅優先探索でも深さ優先探索で解くこともできます。ただ問題によっては幅優先探索が適切であったり、逆に深さ優先探索が適切である場合もあります。

簡単にまとめるとこんな感じです。

幅優先探索も深さ優先探索も最短経路アルゴリズムとしても活用できます。

ただ探索空間 (グラフのサイズ) 自体がとても大きいが、解がスタートから近いところにある場合は幅優先探索が適しています。

それに対して解がスタートから遠いところにある場合は、幅優先探索で調べようとすると探索範囲が広がりすぎてすべてをしらみつぶすことが現実的でない場合は深さ優先探索をつかって適切な枝刈りをしたり探索順序を工夫することで高速に解を求めることができる場合があります。

「グラフの頂点の順序に意味がある場合」とはどのような場合でしょうか? 例えば辞書順最小な経路から順番に探索したい場合では深さ優先探索が効果的です。

また深さ優先探索は再帰呼び出しで短く処理を書くことができます。再帰呼び出しを繰り返すと同じ引数で何度も呼び出しが発生して処理にかかる時間が急激に増えてしまう場合があります。このような場合はメモ化再帰といって処理結果を別のところにメモしておき、また同じ引数が渡されたときは計算はしないでメモしておいた値を返すことで処理にかかる時間を減らすことができます。

問題を解いてみる

Lake Counting (POJ No.2386)

島探し

似たような問題で以下のような問題があります。

島探し (paizaランク S 相当)

列の数がM、行の数がNの表があります。表の各マスは白か黒で塗られています。
黒で塗られたマスが上下左右で隣接している時、その黒マスの塊をまとめて「島」と呼びます。
島の数を計算して出力するプログラムを作成して下さい。

1行目には、列の数Mと行の数Nがスペース区切りで入力されます。
2行目以降のN行には、スペース区切りでM個の数字が入力されます。 各行は’0’が白、’1’が黒のマスをそれぞれ表します。

入力
N M
A_1
A_2

A_N
(ただし 1 ≦ N, M ≦ 100, A_i は M 個の半角スペースで区切られた ‘0’ または ‘1’)

これは黒の部分を探して見つかったら上下左右の黒の部分を白に塗り替える。
その処理が完了したらそれ以外に黒の部分がないか調べる。
見つかったらすべてが白になるまで繰り返す。
繰り返した数が島の個数。

これでよいのではないでしょうか?

幅優先探索で解くならこれでいいのではないでしょうか?

深さ優先探索で解くならこれでいいのではないでしょうか? Stackを使うのではなくDFSメソッドを再帰呼び出しをしています。

どちらもテストは通りました。実行時間の差もほとんどありません。

この問題は paizaランク S 相当 の問題なのですが、AtCoder ではこのレベルの問題ができたとしてもザコレベルの扱いです。ぐぬぬぬぬ。

埋め立て

B – 埋め立て

とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されました。埋め立てによって島を繋いで、1 つの島にしてしまいたいのですが、1 マスを埋め立てた時に 1 つの島にできるかを判定してください。全体は 10マス × 10マスで固定です。

入力
島国の地図が 10 行にわたって与えられる。
各行は 10 文字からなり、o は陸地を、x は海を表す。
陸地と海が少なくとも 1 マスは存在することが保証される。

入力例
xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx

出力例
YES

これは一番上の行を1行目と表現すると 上から6行目、左から5列目 を埋め立てることで全体を一つの島にすることができます。

どうやってやればよいのでしょうか? 全体は10×10と狭いので、海の部分を見つけたらとりあえずその部分を埋め立てて全体が一つになっているかを調べます。全探索で二重ループと幅優先探索をダブルで使って解決する問題です。

D – Bombs

D – Bombs

縦 R 行横 C 列の盤面があります。上から i 行目、左から j 列目のマスを (i, j) と表します。

(i, j) の現在の状態が文字 B[i, j] として与えられます。 . は空きマス、# は壁があるマスを表し、1, 2, …, 9 はそれぞれ威力 1, 2, …, 9 の爆弾があるマスを表します。

次の瞬間に、全ての爆弾が同時に爆発します。 爆弾が爆発すると、爆弾があるマスからのマンハッタン距離がその爆弾の威力以下であるような全てのマス(その爆弾があるマス自体を含む)が空きマスに変わります。

(r_1, c_1) から (r_2, c_2) までのマンハッタン距離は |r _1 – r _2| + |c _1 – c_2|です。

爆発後の盤面を出力してください。

入力されるデータ
R C
B[1,1] B[1,2] … B[1,C]
B[2,1] B[2,2] … B[2,C]
 …
B[R,1] B[R,2] … B[R,C]

(ただし、1 ≦ R, C ≦ 20
B[i,j] は ., #, 1, 2, …, 9 のいずれかである)

爆発の影響をうける部分をどうやって取得するかですが、幅優先探索を何回繰り返したかを数えることができるようにします。

その他の注意点として、爆発の影響はそれぞれの爆弾で独立しているので爆発で他の爆弾を消してしまわないことが挙げられます。

グラフは木になっているか?

B – バウムテスト

バウムテストとは、被験者に「木」の絵を描かせることで被験者の心理状態を読み取る心理検査である。この検査を受けた高橋君は N 個の頂点と M 本の辺からなる無向グラフを描いた。このグラフの連結成分のうち木であるようなもの、すなわち閉路を持たないものの個数を求めよ。

あー、ありましたねー。高校生だったときの話。保険室の前にはタバコを吸うとこうなる、ヘビースモーカーの肺のなかはこんなふうに真っ黒…みたいなことを書いたポスター(?)のようなものが貼ってありましたが、そのなかに木の絵を書かせることで被験者の心理状態がわかるというものもありました。自信満々の人が書く木にはこんな特徴がありますとか、心に闇を抱えた人が書く木にはこんな特徴がありますとか。

さて、解法。木であるならある頂点から出発した場合、バックをしないのであればかつて訪問した頂点が別の頂点からもつながっていたということはありません。そこでバックをしないので末端まで訪問できるかどうかを調べます。

またこの問題ではすべての頂点は連結しているとは書いていません。そこで未訪問の頂点を探してそこから幅優先探索で連結しているすべての頂点をすべて探索する、これを未訪問の頂点がなくなるまで繰り返します。また連結しているグラフが見つかったらそのなかに閉路が存在しないかを確認します。