読者です 読者をやめる 読者になる 読者になる

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

問題

B: リモコン - AtCoder Regular Contest 001 | AtCoder

解き方

貪欲法でも解けるが、境界線を考慮するのが面倒。そんな時は幅優先を使って全列挙してしまう。

幅優先探索とは

幅優先探索とは、複数の選択肢がある時に、全ての選択肢を順番に試していくというものだ。今回の問題では、リモコンでの操作が6つある。これらの操作を片っ端から順番に行っていく。

幅優先の探索順序は、ルートノードから浅いノードを順番に探索していく。よってリモコンの操作回数とループ回数を対応した時に、初めて条件に当てはまるループ処理の時のループ回数が今回の問題の解になる。

キューを用いた幅優先探索

キューを用いた幅優先探索は以下の流れになる。

  1. キューを用意
  2. 評価対象の初めのノードをキューにadd
  3. キューが空になるまで繰り返し
    1. キューから先頭のノードを取り出す
    2. ノードから次の選択肢を選んだ状態の新しいノードを作成
    3. 上記で作成したノードをキューにadd

ソースコード