ABC204 A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder - Qiita

C - Tour BFS(幅優先探索)を使います。 本問についてではないですが、BFSのやり方については動画で詳しく解説しています。ぜひ御覧ください。 都市1,都市2,...都市Nをスタート地点とした時、到達可能な都市の数をそれぞれ数えればよいです。 到達可能な都市を数えるためにBFSを使います。 BFSはグラフを探索する場合に使用するアルゴリズムです。 本問の場合、スタート都市を引数として指定→そこから到達可能な都市の数を返す関数をつくれば楽です。 BFSの具体的な手順は以下です。 (1)各道路の情報を受け取る (2)スタート都市から到達可能な都市の数を数える変数(count)を用意する(初期値は1、スタート都市→スタート都市へ行けるため) (3)訪問済みかどうかを確認するリスト(visited)を用意する(スタート都市は最初に訪問済としておく) (4)キューを用意する (5)キューにス