Introduction to algorithms with java --Search (breadth-first search)

Article summary

This is a series of articles that I have compiled in my study and memo. The third. This is a continuation of this article. Introduction to algorithms in java-Search (depth-first search) In this article

--Breadth-first search

I will study about.

Breadth-first search

It's also called BFS (breadth-first search). (Breadth: width) I will write this while studying. For the difference from the depth-first search that looks like a tree, see this article "Introduction to algorithms with java-Search (depth-first search)" Please give me.

It seems to be effective for problems such as finding the shortest path of a maze.

It seems to use a data structure called a queue as an implementation method. In depth-first search, "first in, last out" stack, Keep in mind that breadth-first search uses a "first in, first out" queue.

Also, depth-first search could be implemented by recursion, but it seems that it is impossible or difficult to process in the order of queues if it is recursion. Do you use queue? .. I don't want to remember new libraries or types at the beginning of my studies. .. .. I don't feel like I can use it right away. ..

By the way, stacks and cues will appear in the Fundamental Information Technology Engineer Examination, so I think it's okay, but I don't know! For those who say, this article "Extreme stacks and cues! ~ Special feature on ideas and uses ~" seems to be easy to understand, so study it. Let's do it.

For the time being, the example is easy to understand Last time I thought I'd try arc031-b implemented in DFS, but it may not fit BFS. So I will try another example.

Example: AtCoder --agc033-a "Darker and Darker"

H　W
A11 A12 ... A1W
:
AH1 AH2 ... AHW

[Answer example]

main.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// height
		int h = sc.nextInt();

		// width
		int w = sc.nextInt();

		//State of squares
		char[][] masu = new char[h][w];

		//Prepare BFS Queue
		Deque<XY> q = new ArrayDeque<>();

		//Receive input& '#'EnQueue
		for (int i = 0; i < h; i++) {
			masu[i] = sc.next().toCharArray();
			for (int j = 0; j < w; j++) {
				if ('#' == masu[i][j]) {
					q.add(new XY(i, j, 0));
				}
			}
		}

		// ans
		int max_depth = 0;

		//BFS main processing
		for (;;) {
			//Infinite loop start

			//Exit conditions
			if (q.size() < 1) {
				break;
			}

			//queue to dequeue
			//poll method fetches from queue&Remove from queue
			XY xy = q.poll();
			int x = xy.x;
			int y = xy.y;
			int depth = xy.depth;

			//Record the number of operations
			if (depth >= max_depth) {
				max_depth = depth;
			}

			//Make the area around the current position black
			if (x + 1 < w && masu[y][x + 1] == '.') {
				//Right square
				masu[y][x + 1] = '#';
				q.add(new XY(y, x + 1, depth + 1));
			}
			if (x - 1 >= 0 && masu[y][x - 1] == '.') {
				//Left square
				masu[y][x - 1] = '#';
				q.add(new XY(y, x - 1, depth + 1));
			}
			if (y + 1 < h && masu[y + 1][x] == '.') {
				//Lower square
				masu[y + 1][x] = '#';
				q.add(new XY(y + 1, x, depth + 1));
			}
			if (y - 1 >= 0 && masu[y - 1][x] == '.') {
				//Upper square
				masu[y - 1][x] = '#';
				q.add(new XY(y - 1, x, depth + 1));
			}

		}

		System.out.println(max_depth);

	}
}

class XY {
	int y;
	int x;

	int depth;

	XY(int y, int x, int d) {
		this.x = x;
		this.y = y;
		depth = d;
	}
}

It is like this. The policy is as follows.

--In the initial state, put the information of the black square in the Queue. (Coordinates, how many times it turned black (= depth)) --Get information from the Queue and search for the squares on the top, bottom, left, and right of that coordinate. If it is white, make it black, increment the depth, and store it in the Queue. If it's black, I don't do anything. --Repeat until there is no data in the Queue (≒ all black).

In this order, the depths are always 0, 1, 2 ... and they enter the Queue in order, so the depth when it turns black is the minimum depth of that square, so once it turns black, it's OK. I am grateful for that.

By the way, is this a variant of breadth-first search, or is it classified as a type of BFS with multiple starting points? It seems to be done.

I learned how to use Queue rather than breadth-first search. Lol I think Deque's poll method is often used, so I definitely want to remember it.

I'd like to visually see the movement when implementing breadth-first search this time as well, but since I learned from the previous article (I thought you could understand it, w) I will stop. ** I have written comments in the code in an easy-to-understand manner, so please follow them. ** **

If this is written for the time being, it seems that the application will work. The rest is a problem exercise. After learning the theory, practice it repeatedly and settle in yourself. I want to keep up with the numbers.

That's all for this time. Next time, I will touch on bit full search. looking forward to!