(dev)juginon-blog

勉強したこと、趣味のこと。

【くどすぎる解説】深さ優先探索・幅優先探索【python】

こんにちは！お久しぶりです、毎月月末になると「あっ、ブログそろそろ更新しないと…」と思いギリギリで更新しているじゅぎのんです。

最近（4月から）AtCoderを始め、現在もう少しで茶色に到達できそうな僕です。

就活を始めるまでにはある程度の色に、アルゴリズムについては一通り大丈夫と言えるようになりたい！

AtCoder強者の友人達にいろいろと教えてもらいながら頑張っています（友人たち本当にありがとう）。

友人達の解説はすごくわかりやすいのに、ネットで調べるとあまりにも意味不明な解説とコードが多い（自分の読解力が足りなさすぎる）ので、

今回から【くどすぎる解説】シリーズということで完全に自分のための備忘録として復習がてらいろんなアルゴリズムのコードをクッソくどい解説文を入れながら書いていきたいと思います。

使用言語はpythonです。おそらく強者から見ると「なんでそこそんなコードで実装してんの」とか思われるかもしれないですが自分の備忘録なので指摘するなら優しくしてください（心が弱いので）。

第一回の解説は深さ優先探索と幅優先探索です。

深さ優先探索

DFSですね。くどすぎると言っても深さ優先探索がどんなものかはさすがに知っているので割愛します。深さを優先して探索するやつです。

具体的な問題だと、AtCoder Typical Contest 001 A - 深さ優先探索

atcoder.jp

ですね。これ解説付きなのでこれ見ろよって話なんですが（ていうかこっちの方が多分わかりやすい）。

入力

4 5
s####
....#
#####
#...g

"4"が縦の長さ、"5"が横の長さ。"s"はスタートで、"g"はゴール。"#"は壁で進むことができず、"."は道で進むことができます。道を通ってsからgまで行くことができれば"Yes"を返し、gまでたどり着けない場合は"No"を返します。

回答と解説

import sys
sys.setrecursionlimit(10 ** 9)
HW = input().split()
H,W = int(HW[0]), int(HW[1])
S = [input() for _ in range(H)]
 
reached = [[False] * W for i in range(H)]
 
def search(x,y):
    #迷路の外か壁の場合は何もしない
    if(x < 0 or H <= x or y < 0 or W <= y or S[x][y] == "#"):
        return
    #以前に到達していたら何もしない
    if(reached[x][y]):
        return
    
    #到達した
    reached[x][y] = True
    
    #4方向を試す
    search(x+1,y)
    search(x-1,y)
    search(x,y+1)
    search(x,y-1)

for i in range(H):
    for j in range(W):
        if(S[i][j] == "s"):
            StartX = i
            StartY = j
        if(S[i][j] == "g"):
            GoalX = i
            GoalY = j
 
search(StartX,StartY)
if(reached[GoalX][GoalY] == True):
    print("Yes")
else:
    print("No")

まず

import sys
sys.setrecursionlimit(10 ** 9)

これですね。深さ優先探索をするときは再帰を使うんですが、なんかpythonだと再帰の回数が多くなるとエラーがでてしまうようで、それを回避するためにこのコードを入れています。sys.setrecursionlimit() で再帰回数の上限を変更することができます。まあとりあえず10の9乗にしとけば大丈夫だろ…ってやったら通りました。ここの数字は特に何も考えてません。

HW = input().split()
H,W = int(HW[0]), int(HW[1])
S = [input() for _ in range(H)]

reached = [[False] * W for i in range(H)]

入力です。"H"を縦、"W"を横の長さ。Sは二次元配列でH行読み込んでます。 reachedは探索を終えたか終えていないかをboolでいれておく二次元配列。

一旦関数の def search(x,y): を飛ばして、実行順で進んでいきます。

for i in range(H):
    for j in range(W):
        if(S[i][j] == "s"):
            StartX = i
            StartY = j
        if(S[i][j] == "g"):
            GoalX = i
            GoalY = j

ここは単純にスタートの位置とゴールの位置を見つけるためのコードです。"i"が行、"j"が列で、二次元配列Sに"s"があればStartX,Yにi,jを入れる。同様に"g"があればGoalX.Yにi,jを入れる。

search(StartX,StartY) ここでsearch関数が呼び出され、先ほど飛ばした部分に入ります。

def search(x,y):
    #迷路の外か壁の場合は何もしない
    if(x < 0 or H <= x or y < 0 or W <= y or S[x][y] == "#"):
        return

xにはStartXが、yにはStartYが入ってきます。コメントに書いてありますがここのif文は迷路の外か壁かを判定しています。

  • 「迷路の外」… x < 0 or H <= x or y < 0 or W <= y
  • 「壁」… S[x][y] == "#"

ですね。ここで自分でもは？ってなったのが、xは縦軸、yは横軸となっている部分です。自分で実装してて意味わからなくなるのほんとバカなんですが、x軸は横でy軸が縦だから H <= y or W <= x じゃね？って思ってしまったんですが、さきほどのStartX,Yを見ると

"i"が行、"j"が列で、二次元配列Sに"s"があればStartX,Yにi,jを入れる。

としているのでxが縦でyが横で合っていますね。縦横とxyを合わせたい場合はStartXにj,StartYにiを入れるのがいいのかも（それだとこっちのコードがは？ってなってしまいそうですが）。

続きます。

 #以前に到達していたら何もしない
    if(reached[x][y]):
        return

 #到達した
    reached[x][y] = True

コメントの通りですね。reachedは探索を終えたか終えていないかをboolでいれておく二次元配列なので、一番最初は全部Falseです。探索を行った部分は後ろのコードでTrueになるので、以前に到達していたらreturnされて終わりです。

#4方向を試す
    search(x+1,y)
    search(x-1,y)
    search(x,y+1)
    search(x,y-1)

4方向を試します。ここでやっていることは、例えば"s"が2行目3列目にあったとすると、

  • 3行目3列目を探す
  • 1行目3列目を探す
  • 2行目4列目を探す
  • 2行目2列目を探す

ですね。ここの順番は特に関係ありません（今回の問題は）。再帰なのでここで4つのルートに分岐して、また分岐した先で4つのルートに分岐して…と続きます。

ただ、再帰元の場所は少なくともすでに探索済みなので、reachedにTrueが入っておりなにも起こらないので、実質3つの分岐ということになります。

これで関数部分終了。最後に、

if(reached[GoalX][GoalY] == True):
    print("Yes")
else:
    print("No")

"g"が書いてあった部分がTrueになっていれば、探索し終わった=そこまで進むことができるということになり、"Yes"を返す。もしFalseだったら"No"を返す。

簡単ですね。さすがに書いてて「くどすぎるだろ…」と思いました。まだまだくどくいきます。

幅優先探索

BFSですね。くどすぎると言っても幅優先探索がどんなものかはさすがに知っているので割愛します。同じ階層を優先して探索するやつです。

具体的な問題だと、AtCoder Beginner Contest 168 D - ..(Double Dots)が最近で幅優先を使いました。

atcoder.jp

入力

4 4
1 2
2 3
3 4
4 2

一行目の左側の"4"が部屋の数、右側の"4"が通路の数。二行目以降は通路が繋ぐ部屋を指します。

つまり、この入力だと

f:id:ogijunchang:20200530204135p:plain

こうなりますね。そして、部屋1以外のすべての部屋から、最短で部屋1に行く時、通るべき部屋の番号を各部屋に道しるべとして置きます。

つまり、上の入力例でいうと、

  • 部屋2から1に行く時 : 直接1に行けるから、"1"を置く。
  • 部屋3から1に行く時 : 3 -> 2 -> 1と行くのが最短なので、"2"を置く。
  • 部屋4から1に行く時 : 4 -> 2 -> 1と行くのが最短なので、"2"を置く。

よって、出力は

Yes
1
2
2

となります（1にたどり着ける場合はYesを出力）。

回答と解説

N, M = map(int, input().split())
link = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    link[A-1].append(B-1)
    link[B-1].append(A-1)
visited = [False for i in range(N)]
result = [0] * N
Q = [0]
visited[0] = True
#Qに要素がなくなるまで
while Q:
    #一番上の要素をpop
    v = Q.pop(0)
    for i in link[v]:
        if visited[i] == False:
            visited[i] = True
            result[i] = v
            Q.append(i)
print("Yes")
for i in range(1, N):
    print(result[i] + 1)
N, M = map(int, input().split())

最初の行の入力。Nは部屋の数、Mは道の数。

link = [[] for i in range(N)]

この配列はすぐ下で解説します。

for i in range(M):
    A, B = map(int, input().split())
    link[A-1].append(B-1)
    link[B-1].append(A-1)

ここでは入力と操作を一度に行っています。

M行を1行ずつfor文で読み込んでいきながら、入力の左の数字と右の数字をそれぞれA,Bにいれます。

先ほど作成したlink配列の、A-1番に要素B-1を、B-1番に要素A-1をいれています。

つまりどういうことかというと、道によって繋がっている部屋を添字番号によって管理しているということです（説明が下手）。

上の入力例では、link配列はこのようになります。

link = [[1],[0],[1,3],[1,2]]

  • 部屋1（0番）は部屋2（1番）とのみ繋がっているので、link[0]には1が入る
  • 部屋2（1番）は部屋1（0番）とのみ繋がっているので、link[1]には0が入る
  • 部屋3（2番）は部屋2（1番）と部屋4（3番）に繋がっているので、link[2]には1と3が入る
  • 部屋4（3番）は部屋2（1番）と部屋3（2番）に繋がっているので、link[3]には1と2が入る

といった感じです。番号が-1になっているのは単純に配列の添字が0から始まるからです。

visited = [False for i in range(N)]
result = [0] * N

visitedは深さ優先探索の時と同じように、すでに探索し終わった場所をboolで保存しておく配列です。

resultは今回の出力（各部屋に置く道しるべの数）を保存しておく配列です。問題が変わればこの部分も変わります。

Q = [0]
visited[0] = True

ここから幅優先探索のスタートです。まず、QはFIFOの動作をするいわゆる「キュー」で、探索する添字番号を指します。最初は0番（部屋1）からなので、Qに0をいれます。

visitedは先ほど言ったようにすでに探索した場所の情報を保存するもの。現在0番（部屋1）を探索したので、visited[0]にTrueをいれます。

#Qに要素がなくなるまで
while Q:
    #一番上の要素をpop
    v = Q.pop(0)

if文に配列を入れると、配列に要素がある場合はtrueを返すことを利用してQに要素がなくなるまでのループとして while Q を使用します。

pop(x)を使うと、xにある要素をpopすることができます。キューなので、先頭の要素を出し、vに代入します。ここでは、Q=0しか入っていないので0がvに代入されます。

 for i in link[v]:
        if visited[i] == False:
            visited[i] = True
            result[i] = v
            Q.append(i)

v=0の状態で、for文に入ります。link[0]には、部屋1（番号0）に繋がっている部屋の番号（[1]）が入っているはずです。よって、iには1が入ります。

次に、探索を行ったか判定します。今回はvisited[0]以外はFalseになっているはずなので、if文の中に入ります。

visited[i] = True で探索済みとマーク。

result[i] = v とすることで、「部屋番号iから直接繋がっている部屋番号はv」という情報をいれることができます。つまり、「部屋2（1番）から直接繋がっているのは部屋1（0番）」ということになります。

Q.append(i) で、現在空になっているQ（キュー）にi（1）をappendします。こうすることで、今度は部屋2（1番）から直接繋がっている部屋を探索することができます。

ここまでくるとわかると思いますが、「直接繋がっている部屋」ごとに探索が行われているということは、各階層ごとに探索が行われるということです。

各階層ごとに探索ができるということは、探索する部屋の深さを知ることができるということです。こんな感じに書けば階層がわかります。

result = [-1] * N
result[0] = 0
#Qに要素がなくなるまで
while Q:
    #一番上の要素をpop
    v = Q.pop(0)
    for i in link[v]:
        if result[i] == -1:
            result[i] = result[v] + 1
            Q.append(i)

サイズNの配列すべてに-1をいれたものをresultとし、先ほどのvisitedと同じ役目を果たすようにします。

もし探索されていない（-1）だったら、そこにresult[v]+1を入れることで、先ほど探索された階層+1が現在の階層のノードに入ることになり、深さを調べることができます。

print("Yes")
for i in range(1, N):
    print(result[i] + 1)

そして、最後に結果を出力します。問題文には「どの2部屋間も、通路をいくつか通って行き来できます」とあるので、道しるべが置けない部屋というのは存在しないので必ずYesを出力します。

最後に道しるべをいれたresult配列をprintすることで回答できます。

おわりに

いかがだったでしょうか。（というかここまで読んでくれる人はいるんでしょうか） 文字で起こすとやっぱり自分で理解できていない部分をもう一回確認できるのでとてもいいですね。これからもちょくちょくくどすぎる解説シリーズを更新してみようかなと思います。明日のABC頑張るぞ！