カデット問題/Bのろし
のろし
昔，将軍に仕える忍者が日本中にいました。忍者たちは，何か事件が起きると，火の煙で合図を送る狼煙（のろし）を使って連絡をしました。
上の図で，赤の点は将軍の住んでいるお城です．水色の点は狼煙を上げる場所です。狼煙が見える場所同士を線で結んでいます。
どの点にも，一日中，のろし係が待機しています。狼煙係は，狼煙が見えるとちょうど１分後に狼煙をあげます。
将軍のお城で狼煙が上がると，何分後にすべての場所で狼煙が上がるでしょうか？
- 解説を見る
- 正解は 5分 です。
- 図では，狼煙（のろし）が見える場所同士を線で結んでいます。
- 将軍の住んでいるお城と線で結ばれている場所では，1分後に狼煙があがります。そこで，将軍の住んでいるお城と線で結ばれている場所に 1 と書き込みます。
- 最初に将軍の住んでいるお城で狼煙があがってから2分後には，1 が書き込まれた場所と線で結ばている場所で狼煙があがります。そこで，それらの場所に（1が書かれていなければ）2と書き込みます。
- これをすべての場所に時間が書き込まれるまで繰り返すと次の図のようになります。
- あとは，この図の中から一番大きな値（時間）を探すだけです。
- 解説
- このような問題を解決する際，グラフは有用です。
- グラフは，ある集合の要素を対象（この場合は，狼煙をあげる場所の集合）とし，ある規則でつなぐ／対にする（この場合は，狼煙が見える場所同士ならつなぐ／対にする）ものです。対象を「頂点」と呼び，つながりを「辺」と呼びます。
- 通信網やウェブページのリンク構造などのネットワークを表すのに，グラフは良く用いられます。
- 最短経路を求めるアルゴリズムは，グラフで考えられる問題に対するアルゴリズムの代表例です。
- この解法では，幅優先探索と呼ばれるアルゴリズムを用いました。
- 正解は 5分 です。
注があるものを除き, このサイトの内容物は
