深さ優先探索と幅優先探索についてPythonで考える

こんにちは
今回は迷路を使って深さ優先探索と幅優先探索について考える。
今回使用する迷路

#入力
入力はn行行われる。

• 1行目は迷路のスタート地点とゴール地点
• 2行目は迷路の縦の長さと横の長さ
• 3~n行目は迷路の情報

n-2は迷路の縦の長さ、マスの無いところは#で与えられる。
ex.)

S G
3 5
# B E F G
S A C H #
# D # # #

#出力
出力は3行行われる。
1行目はスタート地点とゴール地点の距離
2行目は探索の回数
3行目はスタート地点からゴール地点へのルート
ex.)

スタート地点とゴール地点の距離：5
探索回数：10
ルート：G <= F <= H <= C <= A <= S

#深さ優先探索

##コードの流れ

1.入力される情報を読み込む
2.スタートを各種リストに追加
3.スタックから取り出す
4.ゴール判定
5.隣接している地点をスタックに追加
6.チェック済リストに入れ3に戻る

##実装

stack

# cording = utf-8
start, goal = input().split()  # スタート地点とゴール地点
height, width = map(int, input().split())  # 迷路縦と横の長さ
maze, stack, checked, route = [], [], [], {}
num_of_t = 0  # 探索の回数
for i in range(height):
    x = input().split()
    maze.append(x) # 迷路
    if start in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width # スタート地点の座標を保存
stack += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = stack, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while stack[-1] != goal:
    stack.pop()
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    for j in range(height):
        if stack[-1] in maze[j]:
            route[stack[-1]] = maze[now_height][now_width]
            now_height, now_width = j, maze[j].index(stack[-1])
print("スタート地点とゴール地点の距離：" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("探索回数：" + str(num_of_t))
print("ルート：", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

##出力結果

スタート地点とゴール地点の距離：5
探索回数：5
ルート：G <= F <= E <= B <= A <= S

#幅優先探索

##コードの流れ
深さ優先探索のstackをqueueに変更

##実装

queue

# cording = utf-8
start, goal = input().split() # スタート地点とゴール地点を入力
height, width = map(int, input().split()) # 迷路の縦と横の長さ
maze, queue, checked, route = [], [], [], {}
num_of_t = 0 # 探索の回数
for i in range(height):
    x = input().split()
    maze.append(x)  # 迷路
    if "A" in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width # スタート地点の座標を保存
queue += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = queue, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while queue[0] != goal:
    place = queue.pop(0)
    tmp = len(queue)
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    if tmp < len(queue):
        for i in range(1, len(queue) - tmp+1):
            route[queue[-i]] = place
    for j in range(height):
        if queue[0] in maze[j]:
            now_height, now_width = j, maze[j].index(queue[0])
print("スタート地点とゴール地点の距離：" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("探索回数：" + str(num_of_t))
print("ルート：", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

##出力結果

スタート地点とゴール地点の距離：5
探索回数：8
ルート：G <= F <= H <= C <= A <= S

#考察
アルゴリズムに関する知識は十分に深められた。
もっと短く書ける人もいるだろうが、現状の自分ではこの様になった。