python アルゴリズム プログラミング 競技プログラミング

深さ優先探索の勉強

はじめに

今までアルゴリズムについて勉強したことが無かったので、休みを機にアルゴリズムの勉強をしました。今回は深さ優先探索について勉強したので、まとめました。
もし間違いがあったり、こうした方がいいなどありましたらご教示お願いいたします。

深さ優先探索とは

深さ優先探索 - Wikipediaによると次のように説明されています。

深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り行う。形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。

今までアルゴリズムについて一切勉強をしたことが無い私にとっては、説明を読んでもよくわからなかったのですが、下記の図を見てなんとなく理解しました。

深さ優先探索 - Wikipedia

とりあえず、スタートから末端まですべての分岐を無視して進んでいき、進めなくなったら進んでいない別の分岐を進んでいくというイメージですかね？

また、Algoful -深さ優先探索には以下のような説明がされていました。

始点のノードを探索待ちスタックに追加する。
探索待ちスタックにノードがあれば取り出す。なければ全ノード探索完了
取り出したノードが目的のノードであれば探索終了
取り出したノードと隣接するノードの内、未探索のノードを探索待ちスタックに追加する。
2の処理に戻る

この説明を元に実装をしてみたいと思います。(ノード、スタックという言葉がわからなかったので、調べました。)

勉強に使った問題

Atcoder Typical Contest 001 の深さ優先探索の問題を教材として使用しました。以下に問題を書きます。

問題

高橋君の住む街は長方形の形をしており、格子状の区画に区切られています。 長方形の各辺は東西及び南北に並行です。 各区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。 また、塀の区画は通ることができません。

高橋君が、塀を壊したりすることなく道を通って魚屋にたどり着けるかどうか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

H W
c0,0 c0,1 c0,W−1
c1,0 c1,1 c1,W−1
:
cH−1,0 cH−1,1 cH−1,W−1

• 1 行目には、街の南北の長さとして整数 H(1≦H≦500) と東西の長さとして整数 W(1≦W≦500) が空白で区切られて与えられる。
• 2 行目からの H 行には、格子状の街の各区画における状態 ci,j(0≦i≦H−1,0≦j≦W−1) が与えられる。
  • i 行目 j 文字目の文字 ci,j はそれぞれ s, g, ., # のいずれかで与えられ、座標 (j,i) が下記のような状態であることを表す。
    • s : その区画が家であることを表す。
    • g : その区画が魚屋であることを表す。
    • . : その区画が道であることを表す。
    • # : その区画が塀であることを表す。
  • 高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。
  • 与えられた街の外を通ることはできない。
  • s と g はそれぞれ 1 つずつ与えられる。

出力

塀を 1 回も壊さずに、家から魚屋まで辿り着くことができる場合は Yes、辿りつけない場合は No を標準出力に 1 行で出力せよ。

ソースコード

言語はpython3を使用しています。

H,W = map(int,input().split())
graph = []
for i in range(H):
  s = input()
  if "s" in s:
    start_point = [i,s.index("s")]
  if "g" in s:
    goal_point = [i,s.index("g")]
  graph.append(s) 

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def DFS(graph,start_point,goal_point):
  not_visited = []
  not_visited=[[True for i in range(W)] for j in range(H)]
  stack = [start_point]#1.始点のノードを探索待ちスタックに追加

  not_visited[start_point[0]][start_point[1]] = False
  while len(stack) != 0:#2.探索待ちスタックにノードが無ければ終了
    now_point = stack.pop()#2.探索待ちスタックにノードがあれば取り出す
    for i in range(4):
      if now_point == goal_point:#3.取り出したノードが目的のノードであれば探索終了
        print("Yes")
        return False
      else:
        serch_point = [now_point[0]+dx[i],now_point[1]+dy[i]]#4.取り出したノードに隣接するノード
        if 0 <= serch_point[0] < H and 0 <= serch_point[1] < W:#4.隣接するノードが迷路の範囲内かどうか判定
          if graph[serch_point[0]][serch_point[1]] != "#" and not_visited[serch_point[0]][serch_point[1]]:#4.未探索のノードを探索待ちスタックに追加
            stack.append([serch_point[0],serch_point[1]])
            not_visited[serch_point[0]][serch_point[1]] = False  
  return True
if DFS(graph, start_point, goal_point):
  print("No")

つまづいたところ

1. x,yの方向を間違えていた
2. 未探索のノードを探索待ちスタックに追加の条件を間違えていた

1についてですが、私の実装の仕方だと下記の図のようなx,yの方向になっていました。

何となく、xが横方向で、y軸が縦方向のイメージを持っていたので気が付くのに時間がかかりました。

2についてですが、if graph[serch_point[0]][serch_point[1]] != "#"の部分を

if graph[serch_point[0]][serch_point[1]] == "."としていました。これだと、周辺に道があれば未探索ノードに追加しますが、ゴールがあった場合に未探索ノードに追加されず、一生ゴールできないという状態になっていました。

1,2ともに気が付けば簡単なミスですが、気が付くのに時間がかかってしまいました...