DFSについて

お久しぶりとなってしまいました。
最近バタバタしていて、ブログに手が付きませんでしたが、これから元のペースに戻したいと思います。

さて、今回はずいぶん前に書くと言っていたDFSについて書きたいと思います。
ちなみに前回の記事はこちらです。
developer-bpeldi2oerkd8.hatenablog.com

DFSとは

DFSとは「深さ優先探索」の略です。深さ優先探索は、グラフなどの深いところを優先してたどっていく方法です。
よくBFS（幅優先探索）と比較されます。
この2つの使い分けなんですが、ただ探索の順番が違うだけなので、極論どちらでも解けると思います。
ですが、明らかにBFSにしたほうがいいという問題があります。
それが、最短距離を求める問題です。
ほかにも、メモリの使用量などの違いがあるみたいです。
(https://pyteyon.hatenablog.com/entry/2019/03/01/211133より)

とにかく、基本はDFSで解き、「最短」などのワードが出たときはBFSで解けばいいようです。

どのように解くのか（Javaの場合）

DFSを使う問題は主に2種類あります。１つが、配列を使う問題、もう1つがグラフを使う問題です。

配列を使う問題は下の図にあるような格子状の環境の時に使います。
このときにint env = new int[height][width]という風にして、情報を保存します。

この問題の解き方は、下のような感じです。
DFSでは、スタックを使います。

Deque<Point> stack = new ArrayDeque<>();
stack.push(スタート地点);

List<Point> direction = new ArrayList<>();
Point down = new Point(-1, 0);
Point left = new Point(0, -1);
Point up = new Point(1, 0);
Point right = new Point(0, 1);

while(!stack.isEmpty()) {
	Point p = stack.pop();
	int h = p.h;
	int w = p.w;

        //訪問済み
	visited[h][w] = true;
 
        //終了条件
        if(条件) {
		//処理
		break;
	}

        direction.clear();
	if(h-1 >= 0)
		direction.add(down);
	if(w-1 >= 0)
		direction.add(left);
	if(h+1 < H)
		direction.add(up);
	if(w+1 < W)
		direction.add(right);

        for(Point dir : direction) {
		int n_h = h + dir.x;
		int n_w = w + dir.y;
 
		Point n_p = new Point(n_h, n_w);
		if(!stack.contains(n_p) && !visited[n_h][n_w] && 壁などの条件) {
			stack.push(n_p);
			//処理
		}
	}
}

グラフを使う問題はグラフと問題文に書いてあったり、図が載っているのですぐにわかります。
下のようなグラフの時、自分で作ったグラフクラスを用いて、Graph g = new Graph(N)のようにし、情報を保存します。

この問題の解き方は、下のような感じです。
使ったライブラリについては、後で紹介します。
ちなみに、これはB - バウムテストのACした自分の解答の一部です。

while(n.size() > 0) {
	Deque<Node> stack = new ArrayDeque<>();
	stack.push(n.get(0));
	boolean isTree = true;
 
        //ここが深さ優先探索
	while(!stack.isEmpty()) {
		Node node = stack.pop();
 
		//訪問済み
		node.visited = true;
		n.remove(node);
 
		for(int i=0; i<node.edges.size(); i++) {
			Node toNode = node.edges.get(i).to;
			if(!stack.contains(toNode)) {
				if(!toNode.visited) {
					stack.push(toNode);
				        toNode.root = node;
				}else if(!node.root.equals(toNode)) {
                                        //閉路判定
					isTree = false;
				}
			}
		}
	}
}

やはり、深さ優先探索の本体を書くのは慣れればすぐなんですが、条件と中の処理で高確率でバグりますね・・・
ここら辺は練習が必要なようです。

使ったライブラリ

使ったライブラリは自作のものです。
いろんなサイトを参考にして、自分で作りました。
こちらのサイトに載せてあるので、よかったら目を通してください。
github.com
今後もこちらに載せていこうと思います。
webの作った作品もこちらに載せようと思います。

ということで、今回もatcoderの記事でした。
正直、書きたいことがたまっていて、あとBFSとWeb開発のことを書きたいです。
このあと、21時からABCが始まるので、結果を残せるように頑張ります。
ABCの結果はこの後載せる予定です。