深さ優先探索でマス目上の全ての経路を列挙する - 文系プログラマーのプログラミング備忘録

「マス目上の経路」とは、例えば以下のようなものです。

f:id:YukiMoto:20190305235022j:plain

画像ではマス目の縁に沿って辿っていますが、今回考えるのはマス目からマス目へと辿る経路です。

画像のマス目では、左下の角から右上の角へと向かう「最短経路」の数は合計 35通りになっています。
今回はその「最短経路」だけでなく、遠回りなども含めた全ての経路を列挙してみたいと思います。

コードが長いので、2つに分けて紹介します。

入力・出力部分

//マス目の大きさ（正方形）
static int size = 5;

//スタート・ゴール地点
static Point s = new Point(0,0), g = new Point(4,4);

void solve () {

	//-1で初期化
	int[][] b = new int[size][size];
	for (int i=0; i<size; i++) Arrays.fill(b[i], -1);

	//再帰関数（初期座標、訪問済み地点記録用配列、歩数）
	rec (s, b, 0);

}

マス目の大きさは 5 x 5 にしています。
かなり小さいように思えますが、「左上から左下に向かう全ての経路」の数は約1万通りにもなります。同条件での「最短経路」の数が 70通りであることを考えると、凄まじい数ですね。

再帰関数部分

static void rec (Point p, int[][] memo, int n) {
	
	//マス目の範囲外なら終了
	if (p.getX()<0 || p.getY()<0 || p.getX()>size-1 || p.getY()>size-1) {
		return;
	}
	
	//探索済みなら終了（もっといい書き方がありそう）
	if (memo[p.getY()][p.getX()]>=0 && !p.equals(s)) {
		return;
	}
	
	//ゴール地点なら、経路と歩数を出力する
	if (p.getX()==g.getX() && p.getY()==g.getY()) {
		memo[g.getY()][g.getX()] = n;
		if (n <= moves) {　//歩数moves以下の経路のみ出力する
			out.println("moves="+n);
			printInt2DArray(memo);
		}
		return;
	}
	
	//訪問済み地点記録用配列をディープコピーする
	int[][] b = new int[size][size];
	for (int i=0; i<size; i++) {
		for (int j=0; j<size; j++) {
			b[i][j] = memo[i][j];
		}
	}
	
	//歩数を入れる
	b[p.getY()][p.getX()] = n;
	
	//四方に伸ばす
	rec(new Point(p.getX(), p.getY()-1), b, n+1);
	rec(new Point(p.getX(), p.getY()+1), b, n+1);
	rec(new Point(p.getX()-1, p.getY()), b, n+1);
	rec(new Point(p.getX()+1, p.getY()), b, n+1);
	
}

おなじみの座標を探索する再帰関数ですが、一つ違うのは、地点が訪問済みかどうかを記録しておく二次元配列を処理の途中でディープコピーしている点です。

このディープコピーをおこなわないと、「ゴールを一度でも発見したら終了する」再帰関数になってしまうようです。迷路を探索する再帰関数などはこちらのパターンですね。
訪問済みかどうかを「再帰関数全体」か「再帰関数の枝ごと」で持つかの違いだと思いますが、まだ詳しくは理解できていません。

出力結果

f:id:YukiMoto:20190306010509j:plain 　　　 f:id:YukiMoto:20190306010513j:plain
f:id:YukiMoto:20190306010506j:plain 　　　 f:id:YukiMoto:20190306010516j:plain