蟻本 §2-1-2 Lake Counting を Python で

蟻本 §2-1-2 Lake Counting を Python で

今回は蟻本の§2-1-2の問題を Python で解説していきたいと思います。こちらは前回解説した 2-1-1部分和問題と全然関連性が見当たらないような問題にも見えますが,同じアルゴリズムである深さ優先探索(DFS)で解くことができます。それでは,まずは問題文から見ていきましょう。
まだ蟻本を購入していない方は,初心者の方でもこの際ぜひ購入してみてください!本を手元に置きながら勉強した方が効率が飛躍的に上がるはずです。



§2-1-2 Lake Counting (POJ No.2386)


問題文

大きさが N×M の庭があります。そこに雨が降り,水溜まりができました。水溜まりは8近傍で隣接している場合につながっているとみなします。全部でいくつの水溜まりがあるでしょうか?(8近傍とは,次の W に対する * の部分を指します。)
 ***
 *w*
 ***

制約

  • N,M ≦ 100

入力

入力は以下の形式で標準入力から与えられる。

N, M
S11 S12 … S1M
S21 S22 … S2M
… … … …
SN1 SN2 … SNM

出力

水溜まりの個数を出力せよ。


入力例

10 12
w . . . . . . . . w w .
. w w w . . . . . w w w
. . . . w w . . . w w .
. . . . . . . . . w w .
. . . . . . . . . w . .
. . w . . . . . . w . .
. w . w . . . . . w w .
w . w . w . . . . . w .
. w . w . . . . . . w .
. . w . . . . . . . w .

出力例

3


解説

DFSの特徴は,一番初めの状態から遷移を繰り返すことでたどり着ける全ての状態を列挙することができ,その結果全ての状態に対して操作が行えるというところにあります。

適当な W から始めて,そこからつながっている W の部分をすべて “." に置き換えていくという操作を行います。この操作を1回と見ると,この操作でひとつながりの水溜まりは全て “." に置き換わるので,操作を行う回数を出力すれば最終的に得たい水溜まりの数が出力できます。

この操作を定義していきます。任意の位置 (x,y) を見たときに,そこが W であればそこから DFS をスタートします。まずはその W を “."に置き換えます。その後に,移動する方向は周囲8マスなのでそれをループで表現し,その移動後の位置を (nx, ny)とします。この (nx, ny) が庭の範囲内で,かつ W であれば,その (nx, ny)の位置でもう一度同じ DFS をするという流れになります。
最終的に DFS ができなくなった状態で,操作の回数を+1すればよいです。

では,解答に移ります。

解答

N,M = map(int, input().split())
field = [list(input().split()) for i in range(N)]

# 現在位置 (x,y)
def dfs(x, y):
    field[x][y] = '.'

    # 移動する8方向をループ
    for dx in range(-1, 2):
        for dy in range(-1, 2):
            # x方向にdx,y方向にdy移動した場所を(nx, ny)とする
            nx = x + dx
            ny = y + dy

            # nxとnyが庭の範囲内かどうかと位置(nx, xy)が水溜まりかどうかを判定
            if 0<=nx<N and 0<=ny<M and field[nx][ny] == "w":
                dfs(nx, ny)

res = 0
for i in range(N):
    for j in range(M):
        if field[i][j] == "w":
            dfs(i, j)
            res += 1

print(res)

いかがだったでしょうか。
計算量は O(N×M) になります。
まだ蟻本を購入していない方は,ぜひ購入してください! C++ で書かれていますが,扱っている問題や類題をこのブログで Python で書き直していくので,手元において本を見ながら勉強した方がプログラミング能力は飛躍的に伸びていくと思います!

他の問題の解説も行っているので,ぜひ見ていってください!

蟻本
蟻本 §2-2-1 部分和問題
蟻本 §2-2-2 Lake Counting