【Python3】2次元深さ優先探索(DFS)

2022/11/14に公開約1,700字

以下の内容はアルゴ式(https://algo-method.com/)を参考にしています。

2次元DFSの手順

2次元DFSとは、グリッドで行うDFSのことです。
手順は1次元の場合と同じです。

  1. 木を作成する
  2. 関数dfsを作成する
  3. ループを回す

木の作成手順

木を作成する手順がやや複雑になります。

  1. 入力を数値に変換する
  2. 辺を張る

入力を数値に変換する

3 5
#.#.#
.###.
#.#.#

[[1, 0, 1, 0, 1],
[0, 1, 1, 1, 0],
[1, 0, 1, 0, 1]]
というふうに変換します。

H, W = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
for x in range(H):
    S = input()
    for y in range(W):
        if S[y] == "#": grid[x][y] = 1
        elif S[y] == ".": grid[x][y] = 0

辺を張る

各グリッドに対し、左上から順に
0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
というふうに番号を振ります。
上下左右のマスが#(=黒)なら辺を張ります。

getnum:グリッドの番号を取得します。
isvalid:存在するマスか判定します。

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def getnum(x, y, H, W):
    return (x * W + y)
def isvalid(x, y, H, W):
    if 0 <= x < H and 0 <= y < W: return True
    else: return False
    
G = [[] for _ in range(H * W)]
for x in range(H):
    for y in range(W):
        if grid[x][y] == 0: continue
        v = getnum(x, y, H, W)
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if isvalid(nx, ny, H, W):
                if grid[nx][ny] == 0: continue
                nv = getnum(nx, ny, H, W)
                G[v].append(nv)


関数dfsの作成手順

seenも同時に作成しました。
内容は1次元と同じです。

def dfs(v, G, seen):
    seen[v] = True
    for v2 in G[v]:
        if seen[v2]: continue
        dfs(v2, G, seen)
    return
seen = [False for _ in range(H * W)]


ループを回す手順

今回は何回の探索で全部の黒いマスを制覇できるか、すなわち塊は何個あるかを調べています。(塊の個数はcountに格納)

count = 0
for x in range(H):
    for y in range(W):
        if grid[x][y] == 0: continue
        v = getnum(x, y, H, W)
        if seen[v]: continue
        dfs(v, G, seen)
        count += 1

Discussion

ログインするとコメントできます