ひとりで勝手にはじめた蟻本読書会 意外と奥が深い全探索 bit全探索 蟻本読書会の続きです。
Contents
幅優先探索と深さ優先探索
幅優先探索と深さ優先探索も全探索のひとつと考えることができます。頂点と頂点が辺でつながっている場合、つながっている辺をたどることで、すべての頂点を訪問することができる（ただしすべての頂点が直接または間接的につながっている場合のみ）のです。
幅優先探索とは？
幅優先探索ではまず出発点を決めます。そして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に置き換えるだけで実装できるのですが、再帰呼び出しを使えばもっと簡略に書くことができます。
適しているのはどちらか？
では幅優先探索と深さ優先探索ではどちらが優れているのでしょうか？ これはケースバイケースです。幅優先探索が適している場合もあるし、深さ優先探索が適している場合もあるし、どちらでも大差ない場合もあります。
基本的に問題をグラフ上（グラフといっても折れ線グラフや棒グラフのことではなく、頂点と頂点間の連結関係を表す辺で構成されるデータ型のこと）の探索問題に帰着できるのであれば、それは幅優先探索でも深さ優先探索で解くこともできます。ただ問題によっては幅優先探索が適切であったり、逆に深さ優先探索が適切である場合もあります。
簡単にまとめるとこんな感じです。
幅優先探索も深さ優先探索も最短経路アルゴリズムとしても活用できます。
ただ探索空間 (グラフのサイズ) 自体がとても大きいが、解がスタートから近いところにある場合は幅優先探索が適しています。
それに対して解がスタートから遠いところにある場合は、幅優先探索で調べようとすると探索範囲が広がりすぎてすべてをしらみつぶすことが現実的でない場合は深さ優先探索をつかって適切な枝刈りをしたり探索順序を工夫することで高速に解を求めることができる場合があります。
「グラフの頂点の順序に意味がある場合」とはどのような場合でしょうか？ 例えば辞書順最小な経路から順番に探索したい場合では深さ優先探索が効果的です。
また深さ優先探索は再帰呼び出しで短く処理を書くことができます。再帰呼び出しを繰り返すと同じ引数で何度も呼び出しが発生して処理にかかる時間が急激に増えてしまう場合があります。このような場合はメモ化再帰といって処理結果を別のところにメモしておき、また同じ引数が渡されたときは計算はしないでメモしておいた値を返すことで処理にかかる時間を減らすことができます。
問題を解いてみる
島探し
似たような問題で以下のような問題があります。
列の数が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’）
これは黒の部分を探して見つかったら上下左右の黒の部分を白に塗り替える。
その処理が完了したらそれ以外に黒の部分がないか調べる。
見つかったらすべてが白になるまで繰り返す。
繰り返した数が島の個数。
これでよいのではないでしょうか？
幅優先探索で解くならこれでいいのではないでしょうか？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
using System; using System.Collections.Generic; using System.Linq; class Program { static bool[,] Map = { }; static int M, N; static void Main() { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); M = vs[0]; N = vs[1]; Map = new bool[N, M]; // 黒の部分（島の構成要素）はtrue for (int row = 0; row < N; row++) { int[] value = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); for (int col = 0; col < M; col++) Map[row, col] = value[col] == 1 ? true : false; } int ans = 0; for (int row = 0; row < N; row++) { for (int col = 0; col < M; col++) { // 訪問されていないマスをみつけたら // 幅優先探索で Map[sy, sx] から上下左右につながっている部分を白に変更する // この処理を何回繰り返したかが存在する島の個数となる if (Map[row, col]) { BFS(row, col); ans++; } } } Console.WriteLine(ans); } // 幅優先探索で Map[sy, sx] から上下左右につながっている部分を白に変更する static void BFS(int sy, int sx) { Queue<int> qx = new Queue<int>(); Queue<int> qy = new Queue<int>(); qx.Enqueue(sx); qy.Enqueue(sy); Map[sy, sx] = false; int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; while (qx.Count > 0) { int x = qx.Dequeue(); int y = qy.Dequeue(); for (int i = 0; i < 4; i++) { // 次に移動できる上下左右のマスの XY座標 を取得する int nx = x + dx[i]; int ny = y + dy[i]; // 配列の範囲外には移動できない if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue; // 白いマス、すでに訪問したマスは訪問しない if(!Map[ny, nx]) continue; // 次に訪問するマスは訪問済みとする // 次に訪問するマスのXY座標をQueueに格納する Map[ny, nx] = false; qx.Enqueue(nx); qy.Enqueue(ny); } } } } |
深さ優先探索で解くならこれでいいのではないでしょうか？ Stackを使うのではなくDFSメソッドを再帰呼び出しをしています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
using System; using System.Collections.Generic; using System.Linq; class Program { static bool[,] Map = { }; static int M, N; static void Main() { // 標準入力を受け取る部分は上のコードと同じなので省略 // 省略 int ans = 0; for (int row = 0; row < N; row++) { for (int col = 0; col < M; col++) { if (Map[row, col]) { DFS(row, col); // Mainメソッドはここを変えただけ ans++; } } } Console.WriteLine(ans); } static void DFS(int y, int x) { Map[y, x] = false; int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue; if (!Map[ny, nx]) continue; Map[ny, nx] = false; DFS(ny, nx); } } } |
どちらもテストは通りました。実行時間の差もほとんどありません。
この問題は paizaランク S 相当 の問題なのですが、AtCoder ではこのレベルの問題ができたとしてもザコレベルの扱いです。ぐぬぬぬぬ。
埋め立て
とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されました。埋め立てによって島を繋いで、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と狭いので、海の部分を見つけたらとりあえずその部分を埋め立てて全体が一つになっているかを調べます。全探索で二重ループと幅優先探索をダブルで使って解決する問題です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { // 2次元配列を定義。海または訪問済みのマスはtrueとする bool[,] isVisits = new bool[10, 10]; for (int row = 0; row < 10; row++) { char[] vs = Console.ReadLine().ToArray(); for (int col = 0; col < 10; col++) { if(vs[col] == 'x') isVisits[row, col] = true; } } int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; // 海であるマスを二重ループで取得する for (int row = 0; row < 10; row++) { for (int col = 0; col < 10; col++) { // 海であるマスがみつかったらそこを埋め立ててみる if (isVisits[row, col] == true) { int sy = row; int sx = col; Queue<int> queueX = new Queue<int>(); Queue<int> queueY = new Queue<int>(); queueX.Enqueue(sx); queueY.Enqueue(sy); // 幅優先探索で埋め立てた部分の上下左右にある陸地をたどっていって // 全部海または訪問済みにできるかやってみる // このときisVisitsの要素を書き換えてしまうと再利用できなくなるので // コピーしたものを使う bool[,] copied = (bool[,])isVisits.Clone(); copied[sy, sx] = true; while (queueX.Count > 0) { int x = queueX.Dequeue(); int y = queueY.Dequeue(); for (int i = 0; i < 4; i++) { int newX = x + dx[i]; int newY = y + dy[i]; if (newX < 0 || newY < 0 || newX >= 10 || newY >= 10) continue; if(copied[newY, newX]) continue; if (isVisits[newY, newX]) continue; copied[newY, newX] = true; queueX.Enqueue(newX); queueY.Enqueue(newY); } } // 幅優先探索で埋め立てた部分の上下左右にある陸地をたどっていって // 全部海または訪問済みになったか確認する // copiedのなかにfalseがひとつでもあったらマス（row, col）を埋め立てても // ひとつの島にはならない bool ok = true; for (int r = 0; r < 10; r++) { for (int c = 0; c < 10; c++) { if (!copied[r, c]) { ok = false; break; } } if (!ok) break; } // 埋め立ての結果、ひとつの島にできるなら"YES"を出力して終了 if (ok) { Console.WriteLine("YES"); return; } } } } // ループを抜けてしまった場合は、どう埋め立ててもひとつの島はできない Console.WriteLine("NO"); } } |
グラフは木になっているか？
バウムテストとは、被験者に「木」の絵を描かせることで被験者の心理状態を読み取る心理検査である。この検査を受けた高橋君は N 個の頂点と M 本の辺からなる無向グラフを描いた。このグラフの連結成分のうち木であるようなもの、すなわち閉路を持たないものの個数を求めよ。
あー、ありましたねー。高校生だったときの話。保険室の前にはタバコを吸うとこうなる、ヘビースモーカーの肺のなかはこんなふうに真っ黒…みたいなことを書いたポスター（？）のようなものが貼ってありましたが、そのなかに木の絵を書かせることで被験者の心理状態がわかるというものもありました。自信満々の人が書く木にはこんな特徴がありますとか、心に闇を抱えた人が書く木にはこんな特徴がありますとか。
さて、解法。木であるならある頂点から出発した場合、バックをしないのであればかつて訪問した頂点が別の頂点からもつながっていたということはありません。そこでバックをしないので末端まで訪問できるかどうかを調べます。
またこの問題ではすべての頂点は連結しているとは書いていません。そこで未訪問の頂点を探してそこから幅優先探索で連結しているすべての頂点をすべて探索する、これを未訪問の頂点がなくなるまで繰り返します。また連結しているグラフが見つかったらそのなかに閉路が存在しないかを確認します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } // 連結リストをつくる List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); // どの頂点とどの頂点が連結しているかを調べて連結リストを完成させる for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // 与えられる頂点番号は 1 からはじまるので 0 からはじまるものに書き換えている int a = vs[0] - 1; int b = vs[1] - 1; // 無向グラフなので a → b なら b → a list[a].Add(b); list[b].Add(a); } int ans = 0; bool[] visits = new bool[N]; Queue<int> queue = new Queue<int>(); Queue<int> queueParent = new Queue<int>(); for (int i = 0; i < N; i++) { // すでに訪問した頂点は無視 if(visits[i]) continue; // 訪問していない頂点がみつかったら訪問済みにする visits[i] = true; // いまから幅優先探索をしようとしているグラフは「木」か？ bool isTree = true; // 訪問する頂点の番号 // 訪問する頂点にどの頂点から来たか？ // （もと来た道をバックしないようにこれも Queue に保存する） // 最初に訪問する頂点には「どこから来たか」は存在しないので不適切な数（-1）をいれる queue.Enqueue(i); queueParent.Enqueue(-1); while (queue.Count > 0) { int x = queue.Dequeue(); int parent = queueParent.Dequeue(); // list[x] は頂点番号 x から移動できる頂点 // ただしもと来た道をバックするのはノーカウント // それ以外でかつて訪問した頂点がある場合は閉路が存在することになる // 閉路が存在することがわかっても探索は続けて、 // これとは連結していない頂点の発見に役立てる foreach (int next in list[x]) { if (next == parent) continue; if (visits[next]) { isTree = false; continue; } visits[next] = true; queue.Enqueue(next); queueParent.Enqueue(x); } } // もし木なら ans をインクリメント if (isTree) ans++; } Console.WriteLine(ans); } } |
