javaでアルゴリズム入門 - 探索編（幅優先探索）

記事の概要

自分の勉強兼メモでまとめている記事シリーズです。第三弾。
こちらの記事の続きです。
javaでアルゴリズム入門 - 探索編（深さ優先探索）
今回の記事では

• 幅優先探索

について勉強します。

幅優先探索

BFS（breadth-first search）とも言うらしいです。（breadth：幅）
これも勉強しながら書いていきますね。木に見立てた深さ優先探索との違いなどはこちらの記事「javaでアルゴリズム入門 - 探索編（深さ優先探索）」をご覧ください。

迷路の最短経路を求める問題などに有効だそうですね。

実装の方法としてはキューというデータ構造を使うようです。
深さ優先探索では「先入れ後出し」のスタック、
幅優先探索では「先入れ先出し」のキューを用いることを覚えておきましょう。

また、深さ優先探索は再帰でも実装できましたが、キューの順番で処理をするのは再帰だと無理or難しいようです。queue使うか。。勉強の初めにあんまり新しいライブラリというか型とか覚えたくないんだけどな。。。すぐに使いこなせる気がしないから。。

ちなみにスタックやキューは基本情報技術者試験でも出てくるので大丈夫だとは思いますが、わからないよ！という方はこちらの記事「スタックとキューを極める！ 〜 考え方と使い所を特集 〜」が分かりやすそうですので勉強しておきましょう。

例題はとりあえず分かりやすいように前回DFSで実装したarc031-bをやってみようかと思ったのですがなんだかBFSには合わないかも、ということで別の例題にしようと思います。

例：AtCoder - agc033-a「Darker and Darker」

問題文・入力例などはここをクリックして表示
　※できるだけ問題リンクを参照してください

---

（セクション開始）
【問題文】
縦 H 行、横 W 列の白黒に塗られたマス目が与えられます。 マス目の状態は A11 からAHW の HW 個の文字で表されており、 上から i 行目、左から j列目にあるマスが黒色のとき Aij は#、 上から i 行目、左から j 列目にあるマスが白色のとき Aij は . となっています。

すべてのマスが黒色になるまで、以下の操作を繰り返し行います。
辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
何回の操作を行うことになるか求めてください。 ただし、最初に与えられるマス目には少なくとも 1 つ黒色のマスが存在します。

【制約】
1≦H,W≦1000
Aij は # または .
与えられるマス目には少なくとも 1 つ黒色のマスが存在する。

【入力】
入力は以下の形式で標準入力から与えられる。

H　W
A11 A12 ... A1W
:
AH1 AH2 ... AHW

【出力】
行われる操作の回数を出力せよ。

（セクション終了）

---

【回答例】

main.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// height
		int h = sc.nextInt();

		// width
		int w = sc.nextInt();

		// マス目の状態
		char[][] masu = new char[h][w];

		// BFSのQueueを準備
		Deque<XY> q = new ArrayDeque<>();

		// 入力を受け取る & '#'のマスをEnQueue
		for (int i = 0; i < h; i++) {
			masu[i] = sc.next().toCharArray();
			for (int j = 0; j < w; j++) {
				if ('#' == masu[i][j]) {
					q.add(new XY(i, j, 0));
				}
			}
		}

		// ans
		int max_depth = 0;

		// BFS主処理
		for (;;) {
			// 無限ループ開始

			// 終了条件
			if (q.size() < 1) {
				break;
			}

			// queueからdequeue
			// pollメソッドはqueueから取り出し & queueから削除
			XY xy = q.poll();
			int x = xy.x;
			int y = xy.y;
			int depth = xy.depth;

			// 操作の回数を記録
			if (depth >= max_depth) {
				max_depth = depth;
			}

			// 現在の位置の周囲を黒にする
			if (x + 1 < w && masu[y][x + 1] == '.') {
				// 右マス
				masu[y][x + 1] = '#';
				q.add(new XY(y, x + 1, depth + 1));
			}
			if (x - 1 >= 0 && masu[y][x - 1] == '.') {
				// 左マス
				masu[y][x - 1] = '#';
				q.add(new XY(y, x - 1, depth + 1));
			}
			if (y + 1 < h && masu[y + 1][x] == '.') {
				// 下マス
				masu[y + 1][x] = '#';
				q.add(new XY(y + 1, x, depth + 1));
			}
			if (y - 1 >= 0 && masu[y - 1][x] == '.') {
				// 上マス
				masu[y - 1][x] = '#';
				q.add(new XY(y - 1, x, depth + 1));
			}

		}

		System.out.println(max_depth);

	}
}

class XY {
	int y;
	int x;

	int depth;

	XY(int y, int x, int d) {
		this.x = x;
		this.y = y;
		depth = d;
	}
}

こんな感じです。
方針としては以下の感じです。

• 初期状態で黒のマスの情報をQueueに入れる。（座標、何回目で黒になったか(=深さ)）
• Queueから情報を取り出して、その座標の上下左右のマスを探索する。白だった場合、黒にして深さをインクリメントし、Queueに格納する。黒だったらなにもしない。
• Queueからデータがなくなるまで(≒全部黒になる)繰り返し。

この順番だと必ず深さ0,1,2...って順番にQueueに入るから黒になったときの深さがそのマスの最小の深さになるから、一回黒になったらOKというところがありがたいです。

ちなみにこれは幅優先探索の亜種というか、スタート地点が複数あるタイプのBFSに分類？されるみたいですね。

幅優先探索というよりはQueueの使い方の勉強になりました。笑
Dequeのpollメソッドはよく使うと思うので是非覚えたいところですね。

今回も一応幅優先探索で実装した際の動きを視覚的にみようかと思いますが前回の記事で懲りたので（というかわかるでしょ？と思ったのでｗ）やめます。
一応わかりやすくコメントとかもコード内に書いてるので是非追ってみてください。

とりあえずこれが書ければ応用効きそうじゃない？
あとは問題演習ですね。理論を学んだら繰り返し実践して自分に定着していきましょう。数をこなしていきたい。

---

今回はここまでです。
次回はbit全探索について触れようと思います。
お楽しみに！