ダイクストラ法を用いて最短経路で目的地に着く
問題
C: 壁抜け - AtCoder Beginner Contest 020 | AtCoder
ソースコード
解説
問題文のxの値を固定し、xが最大となるものを出力する。xが取りうる値の最大値から順番に試し、スタートからゴールまで制限時間内にたどり着けたものを採用する。
まずは全探索を考える。深さ優先探索を使った全探索では、スタートからゴールまでの全ての行き方を全列挙するので、W,Hが小さい値のみでしか有効にならない。よって別の方法を検討する必要がある。そこでダイクストラ法を用いることにする。
ダイクストラ法とは
グラフ理論において、辺の重み付けを考慮しながら、ある地点からのその他の地点までの最短経路を解くための方法である。
今回の問題では#のマスに移動する時にx秒かかり、それ以外のマスに移動する場合は１秒かかる。この移動にかかる秒数が「辺の重み付け」となる。よって、今回の問題にダイクストラ法を適用させるとスタートからゴールまでの最短時間を効率良く算出する事ができる。
ダイクストラ法の計算量について
深さ優先探索に比べ、ダイクストラ法を用いる場合の方が計算量は少なくて済む。それはダイクストラ法を用いた探索では、ある地点から常に最短経路のノードを辿っていくからだ。そのため、目的地まで最短経路ではない経路のパターンは処理しない。一方、深さ優先はゴールまでの経路を全列挙するので、最短経路以外も処理を行う。そのためダイクストラ法の方が計算量が少ない。
ダイクストラ法を使う典型的な問題
AtCoder/TreasureHunt.java at master · algorithmu-mu/AtCoder · GitHub
ダイクストラ法の流れは以下の通りだ。
２文探索木を用いて計算量を減らす
問題を解く方針として、ｘが取りうる最大値から順番に処理していきゴールまで辿り着いた最初のｘを採用するというものだが、ｘの取りうる値が1~Nの場合、最悪な計算量はO(N)となる。しかし２文探索木を用いることでO(logN)まで小さくすることができる。
