PythonでAtCoderの深さ優先探索(DFS)を解いてみた（結果：TLE...）

####目的
・Pythonの勉強がてら、最近競技プログラミングをよくやってます。過去問を解いて行く際に、深さ優先探索でつまづいたので解法をまとめました。
挑戦した問題は、Typical Contest 001のA問題の深さ優先探索です。
https://atcoder.jp/contests/atc001/tasks/dfs_a

解答

class Dfs():
    def dfs(self, h, w, maze, init):
        search_stack = [init] # 初期座標を探索スタックに格納
        fin = [] # 完了スタックを定義
        while search_stack:
            latest = search_stack.pop() # 探索スタックから現在地を抽出
            if maze[latest[0]][latest[1]] == "g": # 現在地がGoalならYesを出力
                print("Yes")
                exit()
            else:
                fin.append(latest) # 探索済の座標を完了スタックに格納
                candi = [(latest[0]-1, latest[1]), (latest[0]+1, latest[1]), (latest[0], latest[1]-1), (latest[0], latest[1]+1)] # 座標候補を定義
                for (ny, nx) in candi:
                    if self.check_range(h, w, ny, nx): # 座標候補が範囲外に出ていないか判定
                        if self.check_wall(maze, ny, nx): # 座標候補が壁ではないか判定
                            if not (ny, nx)  in search_stack and not (ny, nx) in fin: # 検索スタック、完了スタックに座標候補が含まれていないか判定
                                search_stack.append((ny, nx)) # 探索スタックに格納
                                continue
        print("No")                    
        
    def check_range(self, h, w, y, x):
        if x > w-1 or x < 0:
            return False
        elif y > h-1 or y < 0:
            return False
        else:
            return True
    
    def check_wall(self, maze, y, x):
        if maze[y][x] == "#":
            return False
        else: 
            return True

if __name__ == "__main__":
    h,w = map(int,input().split())
    maze = [list(input()) for i in range(h)]
    for y, row in enumerate(maze):
        try:
            init = (y, row.index("s")) # スタート地点を探索
            d = Dfs()
            d.dfs(h, w, maze, init)
            break
        except ValueError:
            pass