再帰関数入門・迷路探索編
再帰関数を用いて迷路を探索し、スタートからゴールにたどりつけるかどうかを判定する。
使用するのは以下の問題。
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)のような問題を解くときに、幅優先探索を使うのだと思う。