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"

Click here to display problem sentences and input examples
* Please refer to the problem link as much as possible

(Section start) 【Problem statement】 It is given black and white squares with H rows vertically and W columns horizontally. The state of the square is represented by HW characters from A11 to AHW. When the square in the i-th row from the top and the j-th column from the left is black, Aij is #, the i-th row from the top, and j from the left. Aij is. When the squares in the row are white.

Repeat the following steps until all the cells are black. All white cells that share one side and have one or more black cells among adjacent cells become black. Find out how many operations you will be performing. However, there is at least one black cell in the first cell given.

[Restrictions] 1≦H,W≦1000 Aij is # or .. There is at least one black square in the given square.

【input】 Input is given from standard input in the following format.

A11 A12 ... A1W
AH1 AH2 ... AHW

【output】 Output the number of operations performed.

(End of section)

[Answer example]

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(;

		// 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] =;
			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) {

			//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));




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!

Recommended Posts

Introduction to algorithms with java --Search (breadth-first search)
Introduction to algorithms with java --Search (depth-first search)
Introduction to algorithms with java --Search (bit full search)
Introduction to algorithms with java-Search (Full search, Binary search)
Introduction to algorithms with java-Shakutori method
[Java] Introduction to Java
Introduction to java
Introduction to java command
Java to play with Function
Connect to DB with Java
Connect to MySQL 8 with Java
[Java] Introduction to Stream API
[Introduction to rock-paper-scissors games] Java
Java to learn with ramen [Part 1]
100% Pure Java BDD with JGiven (Introduction)
[Introduction to Java] About lambda expressions
[Java] Points to note with Arrays.asList ()
[Introduction to Java] About Stream API
Introduction to Functional Programming (Java, Javascript)
Dare to challenge Kaggle with Java (1)
Initial introduction to Mac (Java engineer)
Server processing with Java (Introduction part.1)
Java, arrays to start with beginners
Solving with Ruby, Perl and Java AtCoder ABC 136 D Breadth-first search
[Java] Introduction
Introduction to Java that can be understood even with Krillin (Part 1)
How to compile Java with VsCode & Ant
Introduction to Ruby basic grammar with yakiniku
[Introduction to Java] How to write a Java program
Add Document to Azure Search Service (Java)
Output of the book "Introduction to Java"
Introduction to monitoring from Java Touching Prometheus
[Introduction to Java] Variable declarations and types
Easy to trip with Java regular expressions
Introduction to Java Web Apps Performance Troubleshooting
Introduction to Java development environment & Spring Boot application created with VS Code
Challenge to deal with garbled characters with Java AudioSystem.getMixerInfo ()
Introduction to Robot Battle with Robocode (Environment Construction)
[Java] How to test for null with JUnit
I tried to make Basic authentication with Java
[Introduction to Java] About type conversion (cast, promotion)
Introduction to SWING
How to search multiple columns with gem ransack
Method to search
Try to link Ruby and Java with Dapr
Road to Java Engineer Part1 Introduction & Environment Construction
How to use Java framework with AWS Lambda! ??
For my son who started studying Java with "Introduction to Java" in one hand
[Monthly 2017/04] Introduction to groovy !! ~ Java grammar / specification comparison ~
I want to use java8 forEach with index
Introduction to web3j
How to use Java API with lambda expression
[Java] Get images with Google Custom Search API
Introduction to Micronaut 1 ~ Introduction ~
Getting started with Kotlin to send to Java developers
Introduction to migration
Try to implement TCP / IP + NIO with JAVA
[Java] Article to add validation with Spring Boot 2.3.1.
Measure the distance of the maze with breadth-first search
Easy to make LINE BOT with Java Servlet
Introduction to Doma