ATC001を例にBFS, DFSを復習した

最近のABC176 D-Wizard in Mazeで0-1DFS(?)というものがあって、その時色々てこずってやべえ復習しなきゃとなりました

BFSとかDFSって久しく書いてないと忘れてしまいますね、笑

そろそろミスが起きにくくするためにも、決まった書き方を定着させたい、

ということでATC001 A-深さ優先探索をDFS、 BFSで書いてみました。

問題としてはgridでのスタート地点からゴール地点に到達可能かをYesNoで答えるものです。

ちなみに僕はDFSやBFSは再帰ではなく、while使うやり方が好きです。sys.setrecursionlimit()とかやるのめんどみなので

あとは僕がそもそも再帰があんまり得意ではないのもあります笑

BFSでの実装

from collections import deque
h, w = map(int, input().split())
c = [input() for _ in range(h)]
dh = [-1, 0, 0, 1]
dw = [0, -1, 1, 0]

# 探索する際に毎度、要素にアクセスすると遅くなるため、enumerateでやる
for i, row in enumerate(c):
    for j, grid in enumerate(row):
        if grid == "s":
            start = (i, j)
        if grid == "g":
            goal = (i, j)

# bfsの自分の中での書き方をあらかじめ決めておくとミスが起きにくい
def bfs(start):
    # スタート地点は最短距離が0 
    visited[start[0]][start[1]] = 0
    queue = deque()
    queue.append((start[0], start[1]))
    while queue:
        th, tw = queue.popleft()
        for i in range(4):
            nh, nw = th + dh[i], tw + dw[i]
            """
            queueに入れない条件を並べて最後にそれらif文を抜けることのできたものだけappend
            if文を綺麗な水作るときのフィルターみたいに使う
            andでif文はまとめられますが、自分的にはこの方がこんがらがりにくいです
            """
            # 移動先がグラフ外
            if nh < 0 or nh > h - 1 or nw < 0 or nw > w - 1:
                continue

            # 移動先が壁
            if c[nh][nw] == "#":
                continue

            # もう既に探索済み
            if visited[nh][nw] != -1:
                continue
            """
            今までのif文をすり抜けてきた点だけ探索候補に加える
            スタートからの最短距離をvisitedの値として保持
            """
            visited[nh][nw] = visited[th][tw] + 1
            queue.append((nh, nw))

# -1はまだ探索されていないことを表す
visited = [[-1] * w for _ in range(h)]
bfs(start)
print("No" if not visited[goal[0]][goal[1]] else "Yes") 

自分の勉強のために、たくさんコメントアウトあります笑

上のコードにおいては、単にスタート地点からゴール地点に行けるかどうかの判別だけではなく、最短距離も求められます。

visitedの値がスタート地点からその点までの最短距離を表しています。

ここで、BFSでの特徴として、すでに訪れたことのある地点は、その地点への最短距離が求まっており、更新されることはないです。

この特徴面白いですよね。理由としてはキューの性質上、スタート地点からの距離が短いものから必ず見ることになっているからです。

DFSでの実装

from collections import deque
h, w = map(int, input().split())
c = [input() for _ in range(h)]
dh = [-1, 0, 0, 1]
dw = [0, -1, 1, 0]

# 探索する際に毎度、要素にアクセスすると遅くなるため、enumerateでやる
for i, row in enumerate(c):
    for j, grid in enumerate(row):
        if grid == "s":
            start = (i, j)
        if grid == "g":
            goal = (i, j)

def dfs(start):
    visited[start[0]][start[1]] = 0
    # stackで管理
    stack = []
    stack.append(start)
    while stack:
        th, tw = stack.pop()
        for i in range(4):
            nh, nw = th + dh[i], tw + dw[I]

            # 移動先がグラフ外
            if nh < 0 or nh > h - 1 or nw < 0 or nw > w - 1:
                continue

            # 移動先が壁
            if c[nh][nw] == "#":
                continue

            # 移動先が探索済みの場合
            if visited[nh][nw] != -1:
                # 最短距離を更新する必要がある場合、距離更新してstackにいれる
                # 最短距離を更新するとその点の先でまた最短距離が更新される可能性があるため、stackに詰め込む
                if visited[nh][nw] > visited[th][tw] + 1:
                    visited[nh][nw] = visited[th][tw] + 1
                    stack.append((nh, nw))
                continue

            # 移動先が今まで一度も到達したことがない場合
            visited[nh][nw] = visited[th][tw] + 1
            stack.append((nh, nw))

visited = [[-1] * w for _ in range(h)]
dfs(start)
print(visited)
print("No" if not visited[goal[0]][goal[1]] else "Yes") 

入力例

...s

....

....

.g..

出力

[[3, 2, 1, 0], [4, 3, 2, 1], [5, 4, 3, 2], [6, 5, 4, 3]]

うまくできていますね

BFSとの違いは探索済みの点の最短距離が更新できる場合、距離更新の後に、探索済み候補にもう一度その点をいれることですね

正直、BFSの方が楽に感じます

何かアドバイスがありましたら、お願いします、、！