迷路を解くアルゴリズム〜深さ優先探索（Depth First Search)、幅優先探索（Breadth First Search)

迷路を解くアルゴリズムをpythonで実装した〜深さ優先探索（Depth First Search）

MAZE = [
    '$$$$$$$$',
    '$  $  G$',
    '$$   $$$',
    '$  $   $',
    '$$$$$$$$',
]
WALL = '$'
GOAL = 'G'

MAZE = [list(i) for i in MAZE]

上の値を、' 'を通路、$を壁に見立てた迷路とする。下のプログラムは、迷路のGの地点(goal)を目指し、上下左右への移動を再帰的に繰り返す。いわゆる深さ優先探索（Depth First Search）。
どんどん枝分かれして探索を続けていくが、

1. 調べた場所が壁の場合
2. 調べた場所がもうすでに探索済みの場合
   の場合は、その分岐は終了する。

そして、いずれかの分岐がgoalに辿り着いた時、全ての探索が終了する。

checkedリストをわざわざ作らなくても、調べた場所を全て壁にするようMAZEに直接書き込んでいけば、「進んだ先が壁なら探索終了」という条件節1個ですむことを知った。以下、改良版（2019.7.10）

def solve(MAZE, y, x):
    if MAZE[y][x] == GOAL:
        return [(y, x)]
    MAZE[y][x] = WALL
    for (next_y, next_x) in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
        if MAZE[next_y][next_x] == WALL:
            continue
        route=solve(MAZE, next_y, next_x)
        if route:
            return [(y, x)] + route


solve(MAZE, 1, 3)

以下の結果になる。

[(1, 3), (2, 3), (2, 4), (1, 4), (1, 5), (1, 6)]

そして、これはキューを使った幅優先探索。経路とともに移動にかかる最短コストを求めている。より短い距離で同じ点にたどり着いたなら、探索を続けている。

以下のコードは、下のリンクのatcoderの問題のコードである。

from collections import deque
import math


def bfs():
    h,w,sy,sx,gy,gx=list(map(int,raw_input.split()[:6]))
    maze=list(map(list,raw_input.split()[6:]))
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=math.inf


    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            dist=maze[nexty][nextx]
            if dist!='#':
                if dist>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    print(maze[gy-1][gx-1])