DFSとBFSは典型的なブラウズアルゴリズムである.
DFSはスタックと再帰関数を用いて実現できる.
BFSはキューを用いて実現する.
今から実戦問題を確認してみましょう.

実戦問題冷凍飲料

質問の概要:
N、Mを受け入れ、N*Mサイズの配列に0と1を入力します.1はスペース、0はスペースです.これは総区間数を求める問題です.
この問題は典型的な探索アルゴリズム問題である.
BFSもDFSも使えますが、BFSアルゴリズムを使って実現してみました.
実装コード:

import java.util.*;
import java.io.*;

class Node{
	int x, y;
	Node(int x,int y){
		this.x = x;
		this.y = y;
	}
}

public class Main{
	
	static int[][] cover;
	static int[][] visited;
	static int n ,m , cnt =0;
	static int []dx = {0 ,0 ,-1 ,1};
	static int []dy = {1 ,-1 ,0 ,0};
	static Queue<Node>queue;
	public static void bfs(int x ,int y) {
		queue = new LinkedList<>();
		queue.add(new Node(x,y));
		visited[x][y] = 1;
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			for(int i = 0; i < 4; i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if(cover[nx][ny] == 0 && visited[nx][ny] == 0) {
					queue.add(new Node(nx,ny));
					visited[nx][ny] = 1;
				}
			}
		}
	}
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		cover = new int[n][m];
		visited = new int[n][m];
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			for(int j = 0; j < m ; j++) {
				cover[i][j] = str.charAt(j) -'0';
			}
		}
		for(int i = 0;i < n ; i ++) {
			for(int j = 0; j < m; j++) {
				if(cover[i][j] == 0 && visited[i][j] == 0) {
					bfs(i,j);
					cnt ++;
				}
			}
		}
		System.out.println(cnt);
		
		
	}
}

コードの説明:
まず入力をスキップしてbfsを理解します.bfsはまず隣接ノードを検査し,次に検査する.だからqueueを使って実現して、私も初めてbfsに触れたときに髪を結んだのを覚えています.しかし、構造を知ると、簡単に感じることができます.まず、配列値とアクセスするかどうかを確認します.両方が条件を満たしている場合は、bfs関数を実行します.bfs関数は次のようになります.
まず、値をキューに挿入し、while文を実行して、キューがすべて空になるまで値を繰り返します.Nodeという名前のclassを作成してxy値を保存するのが便利です重要なのは、問題で上下左右に整列して表示されるので、for文を4回回転させることです.そして、上下左右に移動する場合は、フレームから飛び出していないことを確認してください.また、条件が満たされている場合は、キューに再追加することに重点を置きます.

実戦問題.迷宮を探す

質問の概要:
N×Mサイズの長方形の迷宮には何匹もの怪物がいて、それを避けて逃げようとしています.現在位置は(1,1),迷路出口は(N,M)位置にあり,一度に1格移動可能である.モンスターがいる部分は0で、モンスターがいない部分は1で表示されます.迷宮はきっと逃げられる形で現れたに違いない.逃げるために移動しなければならない最小格子数を求める.セルを計算すると、開始セルと最後のセルが含まれます.
入力
第1行は2つの整数N,M(4<=N,M<=200)を与える.次のN行では,迷路の情報をそれぞれM個の整数(0または1)で与える.各数字には入力としてスペースが付いています.また、開始バーと最後のバーは常に1です.
しゅつりょく
1行目に最小移動格子数を出力します.
入力例

5 6
101010
111111
000001
111111
111111

出力例10実装コード:

import java.util.*;
import java.io.*;

class Node{
	int x, y;
	Node(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class main2 {
	
	static int[][] map;
	static int n ,m ,x ,y;
	static int[] dx = {0 ,0 ,-1 ,1};
	static int[] dy = {1 ,-1 ,0 ,0};
	static Queue<Node>queue;
	public static void bfs(int x ,int y) {
		queue = new LinkedList<>();
		queue.add(new Node(x ,y));
		while(!queue.isEmpty()){
			Node node = queue.poll();
			for(int i = 0 ; i < 4 ;i++) {
				int nx = node.x + dx[i];
				int ny = node.y + dy[i];
				if(nx < 0 || nx >= n || ny <0 || ny >= m) continue;
				if(map[nx][ny] == 0) continue;
				if(map[nx][ny] == 1) {
					queue.add(new Node(nx,ny));
					map[nx][ny] = map[node.x][node.y] + 1;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map =new int[n][m];
		for(int i = 0 ;i < n; i++) {
			String str = br.readLine();
			for(int j = 0 ; j < m; j++) {
				map[i][j] = str.charAt(j) -'0';
			}
		}
		bfs(0,0);
		System.out.println(map[n-1][m-1]);
	}
}

コード解釈:迷宮脱出問題は典型的なbfs問題である.最短距離を求めるので,隣接値に移動する方法が必要である.絵で理解しよう

図:https://blog.hexabrain.net/269ブログから転送されます.
1が出発点だと思ってください.冷凍飲料問題とは異なり、冷凍飲料の区間が分かれているのでbfs関数を呼び出し続ける必要があるが、迷宮脱出問題はつながっているので、一度だけ呼び出すだけでよい.
さらに図に戻ると、3から4の部分があります.2つのブランチに分かれており,3に隣接するノードを探す場合は,移動可能なパスを前のノード値+1に設定するだけでよい.次にqueueに挿入し、マイナス記号を繰り返し、以前のノード値+1にします.