ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

【AtCoder版!蟻本】AOJ 1160 How Many Islands?【深さ優先探索】

f:id:ebisuke33:20210317153208p:plain
AtCoder版!蟻本深さ優先探索で類題としてあげられているAOJ 1160 How Many Islands?をPythonで解いていきます。

AOJ 1160

AOJ 1160 How Many Islands?

問題文

陸に対応する二つの正方形領域が,地図上で縦,横または斜め方向に隣接しているなら,一方から他方へ歩いて行くことができる. 陸に対応する二つの領域が同じ島に属するのは,一方から他方へ(一般には別の陸地を経由して)歩いて行ける時であり,またその時のみである. なお,この地図の海域は海で囲まれており,その外側へ歩いて出ることはできない.

与えられた地図を読み取り,この海域に島がいくつあるか数えるプログラムを作成して欲しい.

制約

・ w と h は地図の幅と高さを表す50以下の正の整数
・ci, j は,0 または 1 であり,空白文字1個で区切られる
・ci, j = 0 なら,地図上で左から i 番目,上か ら j 番目の正方形は海であり,ci, j = 1 なら陸である

解答例

import sys
sys.setrecursionlimit(10**7) #再帰回数の上限変更

# マスy,xに隣接する陸を海に置き換え
def dfs(y,x):
    # 現在地を0に置き換え
    field[y][x] = 0
    # 周囲8マスをループ
    for dx in range(-1,2):
        for dy in range(-1,2):
            # 移動後のマスをny,nxとする
            ny = y + dy
            nx = x + dx

            # ny,nxがfield内で陸かどうかを判別
            if 0 <= nx < w and 0 <= ny < h and field[ny][nx] == 1:
                dfs(ny,nx)
    return


while True:
    w, h = map(int,input().split())
    if w == 0 and h == 0:
        break
    field = []
    for _ in range(h):
        array = list(map(int,input().split()))
        field.append(array)
    
    # 島の数
    ans = 0

    for i in range(h):
        for j in range(w):
            if field[i][j] == 1:
                dfs(i,j)
                ans += 1

    print(ans)

解説

地図上の島の数をカウントする問題で、DFSを使って探索していきます。

これまでのDFSの問題とほとんど同じですが…
地図の各マスを全探索して島であればDFSします。
島のマスを海に置き換えて、周囲9マスに島があるか探します。
島があれば、またそのマスを海に置き換えて、という処理を繰り返して周囲に島がなくなれば島の数を1つ増やしていきました。
全探索が終わればすべて海に置き換わり、島の数がカウントできています。
最後に島の数を出力すればOKです。

このプログラムはデフォルトの再帰回数の上限を超えてしまいます。
上限を10^7に変更しないとエラーになりましたので注意してください。



AtCoder版!蟻本(初級編)の記事リンクページはこちら
ebisuke33.hatenablog.com