再帰関数入門・迷路探索編

再帰関数を用いて迷路を探索し、スタートからゴールにたどりつけるかどうかを判定する。

使用するのは以下の問題。

A - 深さ優先探索

import java.util.*;
import static java.lang.System.*;

public class Blog {
	static Scanner sc = new Scanner(System.in);
	
	static int H=sc.nextInt(),W=sc.nextInt();
	static char[][] map = new char[H][W];
	static boolean[][] memo = new boolean[H][W];
	static int sy,sx;
	static int gy,gx;
	
	public static void main(String[] args) {
		
		for (int i=0; i<H; i++) {
			String s = sc.next();
			map[i] = s.toCharArray();
			for (int j=0; j<s.length(); j++) {
				if (s.charAt(j)=='s') {sy = i; sx = j;}
				else if (s.charAt(j)=='g') {gy = i; gx = j;}
			}
		}
		rec(sy,sx);
		System.out.println(memo[gy][gx]?"Yes":"No");
		
		//ここから探索結果表示
		for (int i=0; i<H; i++) {
			for (int j=0; j<W; j++) {
				out.print(memo[i][j]==true?"o":"x");
			}
			out.println();
		}
		//ここまで
	}

	static void rec(int y, int x) {
		if (y<0 || x<0 || H<=y || W<=x) {return;}
		if (map[y][x]=='#' || memo[y][x]) {return;}
		memo[y][x] = true;
		rec(y,x+1);
		rec(y,x-1);
		rec(y+1,x);
		rec(y-1,x);
	}
	
}

入力例4

まず、メインメソッドからスタート地点を引数にして再帰関数を起動する。

その後は、引数の座標に対して、

迷路の範囲外の場合　→　何もしない
壁の場合、あるいは座標が訪問済みの場合　→　何もしない
それ以外　→　訪問済みかどうかを記録する配列memoにtrueを代入、上下左右に分岐

という流れで処理していく。

処理が一通り終わったら（スタート地点から到達することができる全ての座標を探索したら）、ゴールが訪問済みになっているかどうかを調べて、訪問済みならYes（到達可能）、未訪問ならNo（スタート地点からは到達不可能）を出力する。

迷路探索のアルゴリズムでは、以前、幅優先探索のものを紹介した。

迷路探索メソッド - Java初心者の競技プログラミング日記

深さ優先と幅優先、どちらを使えばいいかは問題による。調べてみたところ、最短歩数を求めるような問題では、深さ優先探索は使えないらしい。また、ゴール地点がスタート地点から近ければ近いほど、幅優先探索のほうが有利になるらしい。

結局のところどちらを使えばいいのか……おそらく、単純にゴールに到達可能かどうかを調べるだけなら、深さ優先探索でいいと思う。コードも短くて済むし。高度なことをやる場合、たとえばyukicoderのコレ（No.424 立体迷路 - yukicoder）や、コレ（No.157 2つの空洞 - yukicoder）のような問題を解くときに、幅優先探索を使うのだと思う。