深さ優先探索（DFS）とは？可能な限り深く探索してからバックトラックする方法！

具体例：迷路の探索

例えば、迷路の出口を見つけるためにDFSを使う場合を考えます。迷路は2次元のリストで表され、0は通れる道、1は壁、Eは出口を示します。

コード例（Python）

def dfs(maze, start, visited=None):
    if visited is None:
        visited = set()
    
    x, y = start
    if maze[x][y] == 'E':
        return True
    
    visited.add(start)
    
    # 上下左右の移動方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for direction in directions:
        new_x, new_y = x + direction[0], y + direction[1]
        
        if (0 <= new_x < len(maze) and 0 <= new_y < len(maze[0]) and
            (new_x, new_y) not in visited and maze[new_x][new_y] != 1):
            if dfs(maze, (new_x, new_y), visited):
                return True
    
    return False

# 使用例
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 'E']
]
start = (0, 0)
result = dfs(maze, start)

if result:
    print("出口に到達しました！")
else:
    print("出口が見つかりませんでした。")

コードの解説

1. 関数定義:

   def dfs(maze, start, visited=None):
   

   dfs という名前の関数を定義しています。この関数は、迷路 maze の中で start から探索を開始し、出口を見つけることを目的としています。

2. 初期化:

   if visited is None:
       visited = set()
   

   訪問済みの場所を記録するためのセット visited を初期化します。

3. 現在位置の確認:

   x, y = start
   if maze[x][y] == 'E':
       return True
   

   現在位置が出口 E であるかを確認し、出口であれば True を返します。

4. 訪問済みの記録:

   visited.add(start)
   

   現在位置を訪問済みとしてセットに追加します。

5. 移動方向の定義:

   directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   

   上下左右の移動方向を定義します。

6. 隣接する位置の探索:

   for direction in directions:
       new_x, new_y = x + direction[0], y + direction[1]
       
       if (0 <= new_x < len(maze) and 0 <= new_y < len(maze[0]) and
           (new_x, new_y) not in visited and maze[new_x][new_y] != 1):
           if dfs(maze, (new_x, new_y), visited):
               return True
   

   各移動方向に対して、新しい位置 new_x, new_y を計算し、その位置が迷路の範囲内であり、訪問済みでなく、壁でない場合に再帰的に dfs 関数を呼び出します。出口が見つかれば True を返します。

7. 出口が見つからない場合:

   return False
   

   すべての探索が終了しても出口が見つからない場合、False を返します。

8. 使用例:

   maze = [
       [0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 0, 1, 0],
       [0, 1, 1, 1, 0],
       [0, 0, 0, 0, 'E']
   ]
   start = (0, 0)
   result = dfs(maze, start)
   

   迷路 maze と開始位置 start を定義し、dfs 関数を呼び出します。

9. 結果の表示:

   if result:
       print("出口に到達しました！")
   else:
       print("出口が見つかりませんでした。")
   

   関数の結果に基づいて、出口に到達した場合はメッセージを表示し、到達しなかった場合は別のメッセージを表示します。

まとめ

今回のポイントをまとめます。

• 深さ優先探索とは、可能な限り深く探索してからバックトラックする方法