はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける幅優先探索問題まとめ [BFS, 後退解析]

幅優先探索, BFS

  • queueを使って実装する
  • 参考1 参考2
  • 後退解析
    • 状態が確定した要素から他の要素へ処理を伝搬させていき、全体の状態を確定させる手法
    • 状態が確定した時点でキューに入れることでBFSが達成できる
    • ゲーム問題でもよく用いられる