マツシタのお勉強

幅優先探索

有向非巡回グラフ(DAG)をトポロジカルソートする

有向非巡回グラフ(DAG)とは DAGとは、有向グラフ且つ閉路のないグラフのことである。これは、ある操作の手順を表す時に用いられたりする。DAGはトポロジカルソートをすることができる。 トポロジカルソートとは トポロジカルソートとは、グラフの有向辺の情…

幅優先探索を用いてリモコン操作を最小限に抑える

問題 B: リモコン - AtCoder Regular Contest 001 | AtCoder 解き方 貪欲法でも解けるが、境界線を考慮するのが面倒。そんな時は幅優先を使って全列挙してしまう。 幅優先探索とは 幅優先探索とは、複数の選択肢がある時に、全ての選択肢を順番に試していく…

スタートからゴールまで最短距離で辿り着く(幅優先探索)

問題 C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder ソースコード 解説 問題文に書いてある通り、キューを用いた幅優先探索によって最短経路を算出する。 ポイント1 幅優先探索の流れ 初めにキューに入れるノード(start)の初期化 startを訪問済…