BFSについて

こんにちは。
今回もAtCoderの記事です。
前々回のDFSに続いて、BFSについて書きたいと思います。

ちなみに、DFSについての記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

また、前回のAtCoder Beginner Contestの参加記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

BFSとは

BFSとは「幅優先探索」の略です。
幅優先探索は、グラフなどの深さが浅いほうから均等にたどっていく方法です。
DFSについて - bpeldi2oerkd8の開発日誌でも書いたように、「最短」などのワードがあったときに使います。
DFSとの使い分けは、前回の記事を見てもらえると嬉しいです。

どのように解くのか（Javaの場合）

基本的にDFSとの違いはスタックを使うか、キューを使うかの違いです。
スタックでは、あるノードを取り出した時、そのノードにつながっているものは次にすぐ取り出されますが、キューでは最後に取り出されるので違いが生まれます。

実際に書いてみて、つまづいた点は!queue.contains()を入れ忘れてしまうことですね。
(DFSにも言えることですが)
これを入れないと同じノードを複数回キューに入れてしまうので、おかしなことになります。

以下のコードは迷路の例です。
全体は下にあるgithubにあるので、もし見たいという方がいましたら、目を通していただけると嬉しいです。
github.com

Queue<Point> queue = new ArrayDeque<>();
queue.add(スタート地点);
while(!queue.isEmpty()) {
	Point p = queue.poll();
	int h = p.x;
	int w = p.y;

	if(終了条件) {
                //処理
		break;
	}

	//訪問済み
	visited[h][w] = true;

	direction.clear();
	if(h-1 >= 0)
		direction.add(down);
	if(w-1 >= 0)
		direction.add(left);
	if(h+1 < H)
		direction.add(up);
	if(w+1 < W)
		direction.add(right);

	for(Point dir : direction) {
		int n_h = h + dir.x;
		int n_w = w + dir.y;

		Point n_p = new Point(n_h, n_w);
		if(!queue.contains(n_p) && !visited[n_h][n_w] && 壁でない) {
			queue.add(n_p);
			distance[n_h][n_w] = distance[h][w] + 1;
		}
	}
}

ということで今回もAtCoderの記事でした。
どうやら今度の土日に2回ABCがあるみたいですね。（本当にありがとうございます）
次回までに、2分探索と最近頻出の余りの問題はやっておきたいですね。
個人的にまだ書きたいことが2つほどあるので、早いこと記事にしたいです。
Web開発のほうについても早いうちに記事にしたいと思います。