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

問題

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

解き方

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

幅優先探索とは

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

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

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

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

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

ソースコード