はじめに
前回
25日目
#25
今日はDFSなるものの入門問題を解きます。こちらの記事を参考にしました。
DFSは、深さ優先探索の略です。似ている名前に幅優先探索(BFS)があります。DFSは名前の通り今いるグラフの点から行ける点に進んでいく感じです。詳しい解説
今回の問題はsがどこにあるか指定されていません。ですので、まずは、's'の場所を探します。's'を見つけたら、stackにsの座標を追加します(型はlistではなくcollections.dequeです)。stackは最後に入れた要素が最初に取り出されます。
次に、visited_listのsの座標を1にします。1の意味は0 or 1で探索済かどうかを判断しているます。このvisited_listが探索済な点の集合になります。
ここからがdfsの中身になります。
- stackが空になるまでwhileします。
- 新しいh,w(現在地)をstackからpopで取り出します
- もしh,wが'g'なら'Yes'を返して終了します。
- h,wが'g'でないなら、それぞれの方向に進みます。この問題は[1, 0], [-1, 0], [0, 1], [0, -1]方向。
- 現在地+それぞれの方向で進んだ先の座標を表現します。
- もし進んだ先が問題の外になる場合は考えないので、continueします。
- もし進んだ先が'#'でないand未探索な点ならvisited_list[座標]を1にして、新しい座標をstackに追加します
from collections import deque
h_in, w_in = map(int,input().split())
c = [input() for _ in range(h_in)]
for n1,c_w in enumerate(c):
for n2,c1 in enumerate(c_w):
if c1 == "s":
s_h = n1
s_w = n2
stack = deque([[s_h,s_w]])
visited_list = [[0]*w_in for _ in range(h_in)]
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_in or new_w < 0 or new_w >= w_in:
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))
まとめ
グラフの問題が出た時点でスルーしてたのですがしっかり勉強して解けるようになりたいです。一問だけでは定着しないので、精進していきます。では、また。おやすみなさい