[PYTHON] [At Coder] Solve a typical problem of depth-first search (DFS)

I want to be a competitive professional, so [This site (AtCoder version! Ant book (beginner))](https://qiita.com/drken/items/e77685614f3c6bf86f44#%E4%BE%8B%E9%A1%8C-2 -5-5warshall-floyd-% E3% 82% 92% E4% BD% BF% E3% 81% 86% E5% 95% 8F% E9% A1% 8C) to solve the AtCoder problem and solve the algorithm The foundation is solidified. This time, we will solve AtCoder's A-depth-first search. This is a typical problem of depth-first search (DFS), which is a type of full search.

problem

In a rectangular town in the north, south, east and west, the question is whether you can reach the fishmonger from your house through the road without passing through a fence on the way.

• By the way, if you solve this problem by breadth-first search (BFS), it becomes the shortest path problem without edge weights.

solution

This time, we will solve it by stacking without using recursion. [Wikipedia](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4 % A2) Depth-first search page gives an overview of the algorithm.

As a point to solve,

■ DFS General Part

--Create a stack and put in unvisited nodes --Mark the visited node as visited

• Required when there is a cycle --Remove one by one from the stack and process
• Because it is a stack, "last in, first out". This is what DFS is all about.

■ Part specific to this problem

――I don't know the start position, so check it first (= put it on the stack) --There are four types of nodes connected to the parent node (x, y): (x-1, y), (x + 1, y), (x, y-1), (x, y + 1).

What a place, such as. Below is the python code.

from collections import deque
 
H,W = map(int, input().split())
C = [input() for _ in range(H)]
 
#Check the position of s in advance
for n1,c_w in enumerate(C):
    for n2,c in enumerate(c_w):
        if c == "s":
            s_h = n1
            s_w = n2
            
stack = deque([[s_h, s_w]])  #Create a stack containing only the start position
 
visited_list = [[0]*W for _ in range(H)]
visited_list[s_h][s_w] = 1
 
def dfs(town, visited_list, stack):
    while len(stack) > 0:
        h, w = stack.pop()
        if town[h][w] == "g":
            return "Yes"
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if town[new_h][new_w] != "#" and visited_list[new_h][new_w] == 0:
                visited_list[new_h][new_w] = 1
                stack.append([new_h, new_w])
    
    return "No"
 
print(dfs(C, visited_list, stack))