スタックを用いた深さ優先探索
深さ優先探索は再帰関数を用いることでも実現できますが、今回はスタックを使って実装してみようと思います。ちなみに、深さ優先探索ではスタックというデータ構造（後入れ先出し）を使うのに対して、幅優先探索ではキューというデータ構造（先入れ先出し）を使います。
それでは、さっそく実装していきたいと思います。今回は以下の問題を使います。
A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder
import static java.lang.System.*; import java.util.*; //Pointクラス class Point { int x; int y; Point(int a, int b) { this.x = a; this.y = b; } } //Mainクラス public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { //変数宣言 int h = sc.nextInt(); int w = sc.nextInt(); char[][] map = new char[h][w]; boolean[][] memo = new boolean[h][w]; int sx=0,sy=0,gx=0,gy=0; //二次元配列に迷路を格納、スタート・ゴール地点を設定 for (int i=0; i<h; i++) { map[i] = sc.next().toCharArray(); for (int j=0; j<w; j++) { if (map[i][j]=='s') { sx = j; sy = i; } else if (map[i][j]=='g') { gx = j; gy = i; } } } //上下左右（分岐先）の座標を配列に入れておくと、forループで回して処理できるので便利 int[] dx = {0,1,0,-1}; int[] dy = {-1,0,1,0}; //スタックを作成、スタート地点を先頭に追加し、スタート地点を探索済みにする Deque<Point> stack = new ArrayDeque<Point>(); stack.addFirst(new Point(sx,sy)); memo[sy][sx] = true; //ここからスタックを用いた深さ優先探索 while (!stack.isEmpty()) { Point p = stack.removeFirst(); //先頭の座標を取得後、削除 for (int i=0; i<4; i++) { //forループで、上下左右に分岐させる int x = p.x + dx[i]; int y = p.y + dy[i]; //分岐先の座標が、2つのif文の条件を満たすなら先頭に追加 if (x>=0 && x<w && y>=0 && y<h) { if (map[y][x]!='#' && !memo[y][x]) { stack.addFirst(new Point(x,y)); memo[y][x] = true; //追加した座標を探索済みにする } } } } //ゴール地点が探索済みであれば到達可能 out.println(memo[gy][gx]?"Yes":"No"); } }
Pointクラスについて
座標を格納できるPointクラスを作成して利用すれば、コードを短く簡潔に記述できるのでオススメです。自作する以外にも、Javaにはjava.awt.Pointというクラスが標準クラスとして備わっていますので、そちらを使うのもアリだと思います。Pointクラスのような構造体を使用しない場合は、スタックをx座標用とy座標用の2本用意することでも実現できます。
