Pythonで毎日AtCoder #26 - Qiita

はじめに 前回 25日目 #25 今日はDFSなるものの入門問題を解きます。こちらの記事を参考にしました。 DFSは、深さ優先探索の略です。似ている名前に幅優先探索(BFS)があります。DFSは名前の通り今いるグラフの点から行ける点に進んでいく感じです。詳しい解説 今回の問題はsがどこにあるか指定されていません。ですので、まずは、's'の場所を探します。's'を見つけたら、stackにsの座標を追加します(型はlistではなくcollections.dequeです)。stackは最後に入れた要素が最初に取り出されます。 次に、visited_listのsの座標を1にします。1の意味は0 or 1で探索済かどうかを判断しているます。このvisited_listが探索済な点の集合になります。 ここからがdfsの中身になります。 stackが空になるまでwhileします。 新しいh,w(現在地)