競プロ強くなりたいので、このサイト(AtCoder 版！蟻本 (初級編))を参考に、AtCoderの問題を解いてアルゴリズムの基礎固めしています。今回解くのは、AtCoderのA-深さ優先探索。全探索の一種である深さ優先探索(DFS)の典型的な問題です。
問題
東西南北の長方形の街にて、途中の塀を通らず、道を通って、家から魚屋へたどり着けるかという問題です。
※ちなみにこの問題を幅優先探索(BFS)で解くと、辺の重みなしの最短経路問題になります。
解法
今回は再帰を使わず、スタックしていく方法で解きます。Wikipediaの深さ優先探索のページがアルゴリズムの概要がわかりやすいです。
解くポイントとしては、
■DFS一般的な部分
- スタックを作成し、未訪問のノードを入れていく
- 訪問したノードには、訪問済みの印をつける
※閉路がある場合に必要
- スタックから一つずつ取り出し、処理を行う
※スタックなので「後入れ、先出し」。これがDFSを実現している。
■この問題特有の部分
- スタートの位置がわからないので、初めに調べる（＝スタックに入れておく）
- 親ノード(x, y)に接続しているノードは、(x-1, y), (x+1, y), (x, y-1), (x, y+1)の4通り
といったところでしょうか。
以下、pythonのコードです。
from collections import deque
H,W = map(int, input().split())
C = [input() for _ in range(H)]
# sの位置をあらかじめ調べておく
for n1,c_w in enumerate(C):
for n2,c in enumerate(c_w):
if c == "s":
s_h = n1
s_w = n2
stack = deque([[s_h, s_w]]) # スタートの位置だけ入ったスタックを作成
visited_list = [[0]*W for _ in range(H)]
visited_list[s_h][s_w] = 1
def dfs(town, visited_list, stack):
while len(stack) > 0:
h, w = stack.pop()
if town[h][w] == "g":
return "Yes"
for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
new_h, new_w = h+j, w+k
if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
continue
if town[new_h][new_w] != "#" and visited_list[new_h][new_w] == 0:
visited_list[new_h][new_w] = 1
stack.append([new_h, new_w])
return "No"
print(dfs(C, visited_list, stack))