[Python]DFS（深さ優先探索） Lake Counting (POJ No.2386)

2386 Lake Counting（蟻本）

DFS（深さ優先探索）

DFSは、初期状態から遷移を繰り返すことで辿り着けるすべての状態を生成します。したがって、すべての状態に対して操作を施したり、全状態を列挙したりできます。

解法

適当な W から始め、そこからつながっている部分を . に置き換える操作を繰り返します。1回のDFSで、始めの W とつながっている W はすべて . に置き換わるので、W がなくなるまでに何回DFSを行ったかが答えです。DFSは各地に対して高々1回しか呼ばれないので、計算量は$O(N\times M)$となります。

サンプルコード

from itertools import product

n, m = map(int, input().split())
lake = [input() for _ in range(n)]
# 辞書型で各位置の状態を入力
lakedict = {(i, j):c for i, row in enumerate(lake) for j, c in enumerate(row)}

# 水溜りを乾燥地にする再帰関数
def dfs(i, j):  # (i, j)は現在位置
    # 現在地が W でなければ終了。範囲外のgetは None 
    if lakedict.get((i, j), '.') != 'W':
        return
    # 現在地 W は . におきかえる
    else:
        lakedict[i, j] = '.'
    # 隣接地に再帰dfs
    for di, dj in product((-1, 0, 1), repeat=2):
        dfs(i+di, j+dj)

n = 0  # dfsを呼ぶ回数
for i, j in lakedict:
    if lakedict[i, j] == 'W':
        n += 1
        dfs(i, j)

print(n)