Javaで迷路を幅優先探索（ゴールまでの歩数を求める）

Java で幅優先探索をおこなうには、Queue というデータ構造を使います。

ja.wikipedia.org

キューは先入れ先出し、すなわち、先に入れられたデータから順に取り出されるデータ構造です。
ところてん式といったほうがわかりやすいかもしれませんね。

では、このキューを使って実際に問題を解いてみます。今回解くのは以下の問題です。

atcoder.jp

コードを載せるに先立って、今回のコードの中で使っているクラスや変数などを紹介します。

Pointクラス

class Point{

	private int x;
	private int y;

	Point(int a, int b) {x=a; y=b;}

	int getX() {return x;}
	int getY() {return y;}
	void setX(int n) {x = n;}
	void setY(int n) {y = n;}

}

Pointクラスは平面上の座標を表すクラスです。
Java には標準で java.awt.Point という座標クラスも用意されているので、そちらを使ってもいいと思います。

定数 D4

Point[] D4 = {new Point(0,-1), new Point(1,0), new Point(0,1), new Point(-1,0)};

定数 D4 は、ある座標とその四方にある座標の、位置の差を表す定数です。
これを作っておくと、ある座標の四方の座標を探索するとき、ループを4回まわすだけで探索できるので便利です。

以下が解答コードになります。

void solve () {

	//迷路の縦横の長さを受け取る
	int h = nextInt(), w = nextInt();

	//start,goalを受け取る
	int sy = nextInt()-1, sx = nextInt()-1, gy = nextInt()-1, gx = nextInt()-1;
	Point start = new Point(sx, sy), goal = new Point(gx, gy);

	//迷路を受け取る
	char[][] map = nextChar2DArray(h, w, false); //trueなら番兵付きで確保

	//Queueを用意し、スタート地点を入れる
	ArrayDeque<Point> dq = new ArrayDeque<>();
	dq.add(start);

	//各地点のスタート地点からの距離を記録する二次元配列
	int[][] moves = new int[h][w];

	//スタート地点を"#"で埋めて、探索済みにする
	map[start.getY()][start.getX()] = '#';


	//幅優先探索
	while (dq.size() > 0) {

		//Queueの先頭の座標を取り出し＆削除して、その四方を探索する。
		Point p = dq.removeFirst();

		for (int i=0; i<4; i++) {

			int x = p.getX()+D4[i].getX();
			int y = p.getY()+D4[i].getY();

			if (map[y][x] == '.') {

				//"."であれば探索可能なので、Queueの末尾に追加する
				dq.addLast(new Point(x, y));

				//探索が終わった座標を"#"で埋めて、次回以降探索しないようにする
				map[y][x] = '#';

				//座標pからpの四方の座標への移動距離は、pまでの移動距離+1
				moves[y][x] = moves[p.getY()][p.getX()] + 1;

			}

		}

	}


	//ゴール地点に相当するmovesの値が答え
	out.println(moves[goal.getY()][goal.getX()]);

}

コードの中の、ポイントになる部分をいくつか紹介します。

while (dq.size() > 0)

キューが空になるまでループを回しています。
キューが空になるのは、スタート地点から訪れることのできる全ての座標を探索し終えたときです。

//探索が終わった座標を"#"で埋めて、次回以降探索しないようにする
map[y][x] = '#';

map[y][x] が "." であれば、訪れることが可能と判断されて、探索されてしまいます。
そのため、一度訪れたら、その座標を "#" とすることで二度と探索できないようにしています。
今回は char型配列map のみでやりくりしていますが、
訪れたか訪れていないかを別の配列（boolean型など）で管理することもできます。

//座標pからpの四方の座標への移動距離は、pまでの移動距離+1
moves[y][x] = moves[p.getY()][p.getX()] + 1;

moves のスタート地点には 0 が格納されています。
スタート地点の四方を探索し、もし "." だった場合は、そこまでの移動距離は moves[スタート地点]+1 です。
あとはこれの繰り返しです。いま見返してみると、ちょっとDPっぽいですね。

と、このようにして幅優先探索で迷路が探索され、スタート地点からの歩数が moves に格納されていきます。
では、探索が終わったあとの moves の中身を見てみましょう。

入力例1（もともと壁だった部分は "##" で表示しています）

入力例2

キッチリ探索できてますね。

次回はこの moves をもとに、スタート地点からゴール地点までの道のりを表示するプログラムを書いてみたいと思います。