[Python] Depth-first search and breadth-first search

I learned (somehow) the difference between the two that I didn't understand while studying algorithms, so I decided to explain it. This time, we will use the methods using the data structures of stack and queue, respectively. It does not handle recursion.

What is depth-first search?

Depth-first search (also known as depth-first search, DFS, backtracking method) is an algorithm for searching trees and graphs. The algorithm starts at the root (in the case of a graph, determines which node to root) and searches as much as possible until it backtracks. Also called "vertical search". [From Wikipedia](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7% B4% A2)

image Priority is given to exploring from the deep part of the maze, and when it reaches a dead end, it tries to return to a place that has not been visited yet.

What is breadth-first search?

Breadth-first search is an algorithm used to search for tree structures and graphs in graph theory. The algorithm starts with the root node and searches for all adjacent nodes. Then, the same thing is repeated for each of these closest nodes to find the node to be searched. Also known as "horizontal search". Breadth-first search comprehensively expands and inspects all nodes in the graph in order to find a solution. Unlike the best-first search, heuristics are not used for node search, and the entire graph is searched without considering whether or not it is close to the target node until the target node is found. From Wikipedia

image After exploring all the neighbors of your current location, proceed to the next. You prioritize width over depth.

DFS (Depth-First Search) Using Stack Structure

What is stack

LIFO (Last In First Out) The image of stacking books and taking them in order from the top. (The book that was placed later is taken out first.)

From the example ATC001 A Problem statement The city where Takahashi lives has a rectangular shape and is divided into grid-like sections. Each side of the rectangle is parallel to east-west and north-south. Each section is either a road or a fence, and Takahashi can move the road north, south, east, and west, but not diagonally. Also, the fence section cannot be passed. Determine if Takahashi can reach the fishmonger through the road without breaking the fence.

#===Organize standard input and data used===#
h, w = map(int, input().split())
sx, sy, gx, gy = None, None, None, None
town = []
edge = ['#'] * (w+2) #Surround the top and bottom with a fence
for i in range(h):
    line = list(input())
    line = ['#'] + line + ['#'] #Surround the left and right with a fence
    for j in range(w+2):
        if line[j] == 's':
            sx, sy = j, i+1 #Start coordinates
    for j in range(w+2):
        if line[j] == 'g':
            gx, gy = j, i+1 #Goal coordinates
    town.append(line)
town = [edge] + town + [edge] #Map of the city in this issue
visited = [[False]*(w+2) for _ in range(h+2)] #Record where you visited in the city

#===Depth-first search started===#
stack = [[sx, sy]] #Put the coordinates of the starting point on the stack
visited[sy][sx] = True #The starting point"Visited"To
while stack: #While there is content in the stack
    x, y = stack.pop()
    if town[y][x] == 'g':
        print('Yes')
        exit() #If your current location is the goal'Yes'Is output to end the execution
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] #Next place to visit: top left, bottom right
    for dx, dy in hjkl:
        if (dx<1) or (dx>w+1) or (dy<1) or (dy>h+1) or town[dy][dx] == '#' or visited[dy][dx] is True:
            #Skip if the direction of travel is a fence, outside the city range, or if you have already visited
            continue
        #If not, stack the direction of travel on a new stack and mark it as visited.
        stack.append([dx, dy])
        visited[dy][dx] = True

print('No') #When you can't reach'No'Output

BFS (breadth-first search) using queue structure

What is queue

First In First Out FIFO (First In First Out) Image that people lined up at the cash register are processed from the person lined up first (first in, first out)

From the example ABC007 C Problem statement Takahashi likes the maze. I'm trying to solve a maze on a two-dimensional board that can move up, down, left, and right. First, the size of the board and the coordinates of the start and finish points of the maze are given. Next, a board with information on whether each cell is a passable empty cell (.) Or an impassable wall cell (#) is given. The board is surrounded by wall squares. The start point and the goal point are always empty squares, and you can always reach the goal point by following the empty squares from the start point to the goal point. Specifically, it is advisable to refer to an input / output example. Now he wants to find the minimum number of moves required to solve the above maze. When I was investigating how to find it, I found that a method called "breadth-first search" was efficient. (Partially omitted)

#===Organize standard input and data used===#
r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = [i-1 for i in [sx, sy, gx, gy]] #Correct coordinates to index
maiz = []
for _ in range(r):
    line = list(input())
    maiz.append(line)

#===Breadth-first search started===#
queue = [[sx, sy]] #Queue the starting point
maiz[sy][sx] = 0 #Start from 0 steps
visited = [[False]*c for _ in range(r)] #Make a note of whether you have visited
while queue:
    x, y = queue.pop(0)
    visited[y][x] = True #Make it visited
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] #Next place to visit: top left, bottom right
    for dx, dy in hjkl:
        if (maiz[dy][dx] == '.') and (visited[dy][dx] is False):
            #Queue and record the effort taken if you are able to proceed and have not yet visited
            queue.append([dx, dy])
            maiz[dy][dx] = maiz[y][x]+1

print(maiz[gy][gx]) #Refer to the number of steps recorded at the goal point

Question: About the order of travel direction diagonal direction

Order of travel direction

In the case of 4 directions, there are 24 different orders in total, but the order of the direction of travel is probably anything. (Please let me know if there is a pattern that does not work if you proceed in this order.)

Diagonal direction

I will proceed. Depending on the problem, there is a condition that you can proceed diagonally, so be flexible. AOJ 1160 How many islands are there?