深さ優先探索(DFS)と幅優先探索(BFS)をpythonで実装する

やったこと

AtCoder Typical Contest 001 の A - 深さ優先探索 をpythonで実装してみた。

この問題は、深さ優先探索(DFS: Depth First Search)でも幅優先探索(BFS: Breadth First Search)でも解くことができるため、両方実装した。

また、深さ優先探索については、再帰関数を用いるパターンとスタック(LIFO)を用いるパターンでそれぞれ実装した。

DFS

再帰関数を用いるケース

# A 深さ優先探索 再帰関数
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

def dfs(v_x, v_y, seen_list, c_list):
    if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
        return
    if seen_list[v_y][v_x]:
        return
    if c_list[v_y][v_x] == "#":
        return
    seen_list[v_y][v_x] = True
    dfs(v_x+1,v_y,seen_list,c_list)
    dfs(v_x-1,v_y,seen_list,c_list)
    dfs(v_x,v_y+1,seen_list,c_list)
    dfs(v_x,v_y-1,seen_list,c_list)

h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

dfs(s[0],s[1],seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")

スタックを用いるケース

# A 深さ優先探索 スタック(LIFO)
from collections import deque

def dfs(stack, seen_list, c_list):
    while len(stack)>0:
        v_x, v_y = stack.pop()
        if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
            continue
        if seen_list[v_y][v_x]:
            continue
        if c_list[v_y][v_x] == "#":
            continue
        seen_list[v_y][v_x] = True
        stack.append([v_x+1,v_y])
        stack.append([v_x-1,v_y])
        stack.append([v_x,v_y+1])
        stack.append([v_x,v_y-1])

h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
stack = deque()

for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

stack.append(s)
dfs(stack,seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")

BFS

# A 深さ優先探索 幅優先探索で解く　キュー(FIFO)
from collections import deque

def bfs(que, seen_list, c_list):
    while len(que)>0:
        v_x, v_y = que.pop()
        if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
            continue
        if seen_list[v_y][v_x]:
            continue
        if c_list[v_y][v_x] == "#":
            continue
        seen_list[v_y][v_x] = True
        que.appendleft([v_x+1,v_y])
        que.appendleft([v_x-1,v_y])
        que.appendleft([v_x,v_y+1])
        que.appendleft([v_x,v_y-1])

h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
que = deque()

for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

que.append(s)
bfs(que,seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")