Aizu Online Judge 1160. How Many Islands?：予備知識、解法およびPython 3による解答例
競技プログラミングにおける実装力の強化とアルゴリズムの学習を主目的として、AOJ-ICPCを利用して、ICPC・JAG非公式難易度表に挙げられている問題に取り組んでいます。現時点ではおおむね難易度100-150程度の問題を解いているところです。この記事では、その一環として先ほど私が解いた1160. How Many Islands?という問題について、学習の記録として、その予備知識を概説し、解法およびPython 3による解答例を示します。
予備知識
グラフ理論におけるグラフ
グラフ理論(graph theory)におけるグラフ(graph)は、頂点(vertex)と呼ばれる点と、辺(edge)と呼ばれる線からなる構造です。ここで、
は頂点全体の集合を、
は辺全体の集合をそれぞれ表します。たとえば、次に図示するグラフは、5個の頂点と4本の辺から構成されます。
深さ優先探索
グラフを探索するためのアルゴリズムとして、深さ優先探索(DFS: depth-first search)があります*1。大雑把に言うと、この方法では、探索を開始する頂点から進めるだけまっすぐ進み、行き止まりに到達すれば今までたどってきたうちで最も近い分岐点*2に戻り、そこから探索を始めるという作業を繰り返します。これ以上新たに到達できる頂点がない状態になれば、探索を終わりにします。深さ優先探索の時間計算量はであり、空間計算量は
です*3。次の図における赤い矢印は、上図のグラフに対して深さ優先探索を行う際の探索順の一例を示しています。
wikipedia:深さ優先探索には、深さ優先探索の擬似コードとして、再帰を用いるものとスタックを用いるものが記されています。以下の解答例では、前者に近い方法をとっています。
深さ優先探索の基礎と実装方法を学ぶよい例題として、AtCoder Typical Contest 001の問題A深さ優先探索があります。以下に示すコードは、この問題に付随するスライド深さ優先探索による塗りつぶしを参考にして作成したものです。
解法
以上を踏まえて、1160. How Many Islands?に対する解法について述べます。本問では、地図上における陸をグラフの頂点と、また陸からそれに隣接する陸への移動をグラフの辺とそれぞれみなせば、深さ優先探索を用いることができます。地図上の各マスを順番に調べ、陸のマスが見つかればそこから深さ優先探索を始めます。ここで、探索済みの陸は海に置き換えることで、同じ陸のマスを重複して調べることを防ぎます。探索1回につき1つの島がすべて海となって「塗りつぶされる」ので、探索回数が島の数に一致します。
Python 3による解答例
次のコードは、上述の解法に基づく答案です。上でも述べたように、スライド深さ優先探索による塗りつぶしを参考にして深さ優先探索の処理を実装しました。実装面で留意した点は以下の通りです。
- itertools.productを用いて、多重のforループを一重のforループに置き換える
- 多重のforループから脱出するには工夫が必要である
- Pythonの場合には、多重ループを書くとインデントが深くなる
- 配列の表現にarrayを用いて資源を節約する
- 入力をそのまま配列にせず、zip関数で転置することで、stage[x][y]で左からx番目、上からy番目のマスを指定できるようにする
- stage[y][x]でもよいが、ややわかりにくい
