以下の参考書を元に、TopCoderの対策をしています。

https://amzn.to/3cAQ5wH

今日は、深さ優先探索と、幅優先探索について勉強しました。

深さ優先探索(DFS)

なるべく左に深い点から探索するアルゴリズム.

実装方法

実装では再帰関数を用いる. ここでは、答えを最大化する深さ優先探索の例.

def dfs(now):
  if "nowが終了条件":
    return "nowの答え"
    
  ret = -1
  for i in range("次の状態の個数"):
    next = "i番目の次の状態"
    if "nextが条件を満たしている":
      ret = max(dfs(next), ret)
      return ret

SRM 425 Div2 500

WordPressからの移植でコードフォーマット壊れたので削除

幅優先探索(BFS)

深さの浅い、左側の点から順に探索するアルゴリズム.

実装方法

WordPressからの移植でコードフォーマット壊れたので削除

DFSとBFSの比較

  • 全通りを列挙し、をまとめる必要がある場合は DFS
  • 始点からもっとも近いものを求めたいときは、BFS

Special Thanks