This is a series of articles that I have compiled in my study and memo. This is a continuation of this article. Introduction to Algorithms with java-Search (Full Search, Binary Search) In this article

--Depth-first search

I will study about. I wrote it in the continuation of the previous article.

It's like this from here, but let's proceed. While learning and summarizing. Depth-first search. It seems that it is also called DFS (depth-first-search). By the way, I often see this word. Depth-first search and breadth-first search seem to be useful for searching trees and graphs. I will omit the explanation of trees and graphs. The figure is shown below. (From wikipedia) It's like DFS to search trees in this order with priority on depth.

For those who say, "I don't know what is depth-first!", I think it's one shot if you look at the search order of breadth-first search.

Did you see the difference in numbers? Depth-first search searches in a straight line from the root to a node that has no children, and breadth-first search searches for nodes with a depth of 1 from the root in order.

By the way, there are two types of implementation methods.

--How to use stack (last in, first out data structure) --How to use a recursive function

... I feel like I'm afraid because it's crazy. You can't understand without seeing an example. If you look for a simple example, you can't find an example that you can intuitively understand. .. As shown in the figure above, it's just a way to search in that order! Is it like that? I will understand it while looking at problem examples and solving them. If you can understand it, maybe you can make a simple example?

Example: AtCoder --arc031-b "Landfill"

* Please refer to the problem link as much as possible

(Section start) 【Problem statement】 There was an island country in a certain place. There are several islands in the island nation. A landfill plan has been drafted in this island country, but it has not been decided where to landfill. If possible, I would like to connect the islands by landfill to make one island, but I can't do much. You will be given a map of this island country of 10 squares x 10 squares, so determine if you can make one island when you reclaim one square. However, the area where the squares representing the land on the map are connected vertically and horizontally is called an island.

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

```
\(A1,1\)\(A1,2\)...\(A1,10\)
\(A2,1\)\(A2,2\)...\(A2,10\)
:
\(A10,1\)\(A10,2\)...\(A10,10\)
```

A map of the island nation is given over 10 lines. Each line consists of 10 characters, where o stands for land and x stands for sea. At least one square is guaranteed to have land. At least one square is guaranteed to have a sea.

【output】 Output YES if you can make the whole island into one island by making the sea one square, and NO if you can't. Add a line break at the end of the output. However, output YES even if it was originally one island.

【Input example】 xxxxxxxxxx xoooooooxx xxoooooxxx xxxoooxxxx xxxxoxxxxx xxxxxxxxxx xxxxoxxxxx xxxoooxxxx xxoooooxxx xxxxxxxxxx

(End of section)

I've been studying by looking at other people's sources and various blogs. The policy is as follows. Maybe many people did this.

――Search for one square in 10 * 10 lands, "If you reclaim this one square, you can make the whole into one island." -Count the number of squares on the island by depth-first search from the first selected square. If the number of squares searched at this time is the square of the island received in the first input + 1 square (if the sea is reclaimed), the condition is met.

[Answer example]

` main.java`

```
import java.util.Scanner;
public class Main {
//Map of the island
static char[][] islandMap;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//Map of the island
islandMap = new char[10][10];
//Number of trout on the island
int countIsland = 0;
//Final output
String ans = "NO";
//Receive input and complete the map of the island, count the number of island squares
for (int i = 0; i < 10; i++) {
islandMap[i] = sc.next().toCharArray();
for (int j = 0; j < 10; j++) {
if (islandMap[i][j] == 'o') {
countIsland++;
}
}
}
//Search for squares from the upper left square with a double loop
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
//Island count temporary variable
int countIslandInLoop = countIsland;
//In the case of the sea, make it land. Also increase the number of islands by one
if (islandMap[i][j] == 'x') {
islandMap[i][j] = 'o';
countIslandInLoop = countIsland + 1;
}
/*
*Depth-first search is performed.
*dfsCountIsland ・ ・ ・ The number of land-based islands counted by dfs
*checked ・ ・ ・ Judgment whether the square has been searched by dfs
*/
dfsIslandCount = 0;
boolean[][] checked = new boolean[10][10];
dfs(i, j, checked);
if (dfsIslandCount == countIslandInLoop) {
ans = "YES";
break;
}
//Put back the landfilled square and go to the next loop
if (countIslandInLoop == countIsland + 1) {
islandMap[i][j] = 'x';
}
}
if ("YES".equals(ans)) {
break;
}
}
System.out.println(ans);
}
//Number of squares on land-based islands currently counted by dfs
static int dfsIslandCount;
//Depth-first search
static void dfs(int i, int j, boolean[][] checked) {
//If it is beyond the square, has been searched, or is the sea, change direction.
if (i < 0 || i > 9 || j < 0 || j > 9 || checked[i][j] || islandMap[i][j] == 'x') {
return;
}
//If the square you are searching for is land, increment the land count.
if (islandMap[i][j] == 'o') {
dfsIslandCount++;
}
//Make the current square searched
checked[i][j] = true;
//Search up, down, left and right squares
dfs(i + 1, j, checked);
dfs(i - 1, j, checked);
dfs(i, j + 1, checked);
dfs(i, j - 1, checked);
return;
}
}
```

No, it was really difficult. It's very difficult to put it in a global variable or how to recurse a search.

It doesn't matter, but AtCoder has prepared an example of such an algorithm. AtCoder --atc001-a "Depth-first search"

For the time being, I've used it as the code for this problem, so let's look at the dfs part from above.

I wonder if I can see about 2 squares. First, the example input is as follows:

```
xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx
```

- × is the sea and ○ is the island. The map at this time looks like the following. (Well, you can tell from the character string.)

Let's think about DFS for cell (1) and DFS for cell (2).

In the dfs method of the above code for clarity, The if statement of the first process is "// If it exceeds the square, has been searched, or if it is the sea, change direction." The second process is "// If the cell you are searching for is land, the land count is incremented", The process of No. 3 is "// Make the current square searched", The 4th process is the process of "// Search for squares on the top, bottom, left, and right". (I will explain which one is called each time.)

Let's follow the source. I will mainly explain about moving squares with dfs.

Here is the figure in which the square of ① was reclaimed in the second process.

I also added the values of i and j. Then it's DFS. After making the current cell searched by the 3rd process, proceed to the 4th process. The first thing to be called
`dfs(i + 1, j, checked);`

is. i = 0, j = 0
`dfs(1, 0, checked);`

is not it.
With this, I moved to the square of i = 1, j = 0, but since the destination is the sea, I get caught in the if statement in the first process. It will be returned.

Next, proceed to the second line of the 4th process.
`dfs(i - 1, j, checked);`

Specifically
`dfs(-1, 0, checked);`

is not it.
It moves to the square of i = -1, j = 0 (outside the map) and is returned in the first process.

The same is true for the 3rd and 4th lines. This completes the search for cell ①. It's hard to understand because it's not recursive yet. However, I think it would be good to think from such an easy-to-understand example.

Here is an example of the answer. Let's be enthusiastic and DFS. Here is a figure of landfill with i and j numbers.

After the first call, the red part is called, the movements are programmatically indented and written in order. It feels like recursion when indented. We will start with the fourth process of the first dfs call. ** Let's go all out! !! ** ** Currently (i, j) = (5,4). The order in which they are called, including recursion, is as follows:

`dfs(6, 4, checked);`

`dfs(7, 4, checked);`

`dfs(8, 4, checked);`

`dfs (9, 4, checked);`

← Because it is the sea, it ends`dfs (7, 4, checked);`

← Ended because it was searched on the 02nd line`dfs(8, 5, checked);`

`dfs (9, 5, checked);`

← Because it is the sea, it ends`dfs(7, 5, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(8, 6, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
`dfs(8, 3, checked);`

`dfs (9, 3, checked);`

← Because it is the sea, it ends`dfs(7, 3, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(8, 2, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs (6, 4, checked);`

← Ended because it was searched on the 01st line`dfs (7, 5, checked);`

← Ended because it was searched on the 08th line`dfs (7, 3, checked);`

← Ended because it was searched on the 21st line`dfs (5, 4, checked);`

← End because it has been searched first`dfs (6, 5, checked);`

← Because it is the sea, it ends`dfs (6, 3, checked);`

← Because it is the sea, it ends`dfs(4, 4, checked);`

`dfs (5, 4, checked);`

← End because it has been searched first`dfs(3, 4, checked);`

`dfs (4, 4, checked);`

← Ended because it was searched on the 38th line`dfs(2, 4, checked);`

`dfs (3, 4, checked);`

← Ended because it was searched on the 40th line`dfs(1, 4, checked);`

- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
`dfs (0, 4, checked);`

← Because it is the sea, it ends`dfs(1, 5, checked);`

`dfs(2, 5, checked);`

`dfs(3, 5, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(2, 6, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(1, 6, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(1, 7, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs (0, 5, checked);`

← Because it is the sea, it ends- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
`dfs(1, 3, checked);`

`dfs(2, 3, checked);`

`dfs(3, 3, checked);`

- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(2, 2, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(1, 2, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
`dfs(1, 1, checked);`

- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥ ‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥
- Ended because it has been searched on the 84th line
`dfs (1, 2, checked);`

← 84th line `dfs (2, 5, checked);`

← Ended because it was searched on the 42nd line`dfs (2, 3, checked);`

← Ended because it was searched on the 74th line`dfs (3, 5, checked);`

← Ended because it was searched on the 50th line`dfs (3, 3, checked);`

← Ended because it was searched on the 75th line`dfs (4, 5, checked);`

← Because it's the sea, it's over`dfs (4, 3, checked);`

← Because it's the sea, it's over`dfs (5, 5, checked);`

← Because it's the sea, it's over`dfs (5, 3, checked);`

← Because it's the sea, it's over

** Oh ... it's over ... ** I'm super tired. It wasn't something that people would do by hand. Well, I did it so much, so let's check what kind of movement was being searched for. I tried to express the search order in white letters.

You can see it by looking at the figure, and you can see it by looking at the feeling of loop, but DFS is like "If you can't get to the point, you'll change direction."

I also think that the word "stack" came out, but it feels like this recursion method is exactly the order of the first-in, second-out stacks. Even if you don't use a data structure called a stack, you can see that if you write an implementation recursively, it will be a stack-like process.

Did you understand depth-first search? I could understand a little. (Oh, I'm tired ...)

It's been a long time, so I'll explain breadth-first search again next time. Next time we look forward to! !!

Recommended Posts