AtCoder Beginner Contest 168 [ D - .. (Double Dots) ]をPythonで解く（400点、🟩緑diff）
問題
解答
BFS(幅優先探索)で、あっさり解ける。
BFSの探索をかけて、ans[i]に部屋iの一個前の部屋番号を記録。
ansが一通り揃っているなら、"Yes"の後にまとめて表示。
感想
問題読んで、dfsかbfsだろうな？とは思うが、どっちだろう感ある。
競プロの考察方針の一つとして、典型問題に似ていないかという糸口がある。
今回は、今いる部屋から最短距離で部屋1にたどり着くという条件があるが、最短距離はどのくらいになるだろう。
全ての部屋から部屋1にたどりつくための最短距離を考えたいが、移動が双方向に可能なことから、
部屋1から各部屋にたどりつくための最短距離を考えるのと実質同じであることが言える。
このある始点から移動コスト1で移動したときの最短距離を求めるのは、典型問題であり、
BFSで解けることが知られている。
とあるので、移動コスト指定がとくに無い最短距離問題はBFSと考えて良いのだろうか？
