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