AtcorderABC-Dより先へ行くために代表的なアルゴリズムを勉強した-その3-（DFS、BFS）.md
はじめに
- ABC-Dを解くために、下記のアルゴリズムを勉強しました。
1-1. DFS（再帰） 1-2. DFS（スタック） 2. BFS(キュー)
アルゴリズム
1-1. DFS（再帰）
参考
いつ使うか
深さ優先探索（DFS: Depth First Search）は，状態の遷移が分岐するような処理を実装するのに有効です．過去のコンテストでは，配列 A の要素 A[i] を端から「使う / 使わない」の処理(ABC119 - C)文字集合があって任意の文字列を後ろに結合していく処理(ABC029 - C)など，状態の遷移が分岐する処理（大事なことなので 2 回言いました）を実装するために使われました．DFS が最適解でなくとも，DFS で全探索を行うと解けるという問題は少なくないと思います．
概要
- 深いほうへ進めるだけ進み、進めなくなったら戻るアルゴリズム。
DFS
例題
問題
解法
N=int(input()) ans = 0 def dfs(s): global ans # 再帰探索の打ち切り条件 if int(s) > N: return 0 # 各要素に辿りついた度にしたい処理 if ('7' in s) and ('5' in s) and ('3' in s): ans += 1 # 現在地点から、次に行こうと思えば行けるポイントを全部探し出す s_child_1 = s + '7' s_child_2 = s + '5' s_child_3 = s + '3' # 次に行こうと思えば行けるポイントの下を探索 # '再帰探索の打ち切り条件'になるまで深く行き切ってから、一つ階層を上に戻って横に dfs(s_child_1) dfs(s_child_2) dfs(s_child_3) return ans print(dfs('0'))
1-2. DFS（スタック）
参考
- 同上
いつ使うか
- 同上
概要
- 同上
例題
問題
- 同上
解法
N=int(input()) import os from collections import deque ans = 0 def dfs(s): global ans # スタック準備 q = deque([]) # 探索スタート地点を「探索候補スタック」に積む q.append(s) while len(q) > 0: # スタックが空っぽになるまで # スタックから次の要素を1つ取り出す（pop） p = q.pop() # 各要素に辿りついた度にしたい処理 if ('7' in p) and ('5' in p) and ('3' in p): ans += 1 # 現在地点から、次に行こうと思えば行けるポイントを全部探し出す p_child_1 = p + '7' p_child_2 = p + '5' p_child_3 = p + '3' # 条件を満たすポイントを「探索候補スタック」に追加する if int(p_child_1) < N: q.append(p_child_1) if int(p_child_2) < N: q.append(p_child_2) if int(p_child_3) < N: q.append(p_child_3) return ans print(dfs('0'))
2. BFS（キュー）
参考
- 同上
いつ使うか
幅優先探索（BFS: Breadth First Search）は，「迷路の最短経路の探索」が最も直感的に分かりやすい例だと思います．近いところから万遍なく探索していくイメージです．
概要
- 同じ深さを順に調べ、それがつきたら次の深さに進むアルゴリズム。
BFS
例題
問題
解法
def C_BFS(R, C, sy, sx, gy, gx, c): """ R:行数 C:列数 sy,sx:スタートの座標(sy行sx列) gy,gx:ゴールの座標(gy行gx列) c:迷路の形状(.:通路,#:壁) """ INF = float('inf') sy -= 1 sx -= 1 gy -= 1 gx -= 1 def bfs(maze, row, column, sy, sx, gy, gx): # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある) queue = [] queue.insert(0, (sy, sx)) dist = [[INF for _ in range(column)] for _ in range(row)] dist[sy][sx] = 0 # yが行数、xが列数を意味するときはこの順に書く while len(queue): y, x = queue.pop() if x == gx and y == gy: # ゴール座標と一致するなら break for i in range(4): nx, ny = x + [1, 0, -1, 0][i], y + \ [0, 1, 0, -1][i] # (x,y)の右、上、左、下 if 0 <= nx and nx < column and 0 <= ny and ny < row \ and maze[ny][nx] != '#' and dist[ny][nx] == INF: #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき queue.insert(0, (ny, nx)) # 次に探索する座標 dist[ny][nx] = dist[y][x] + 1 return dist[gy][gx] maze = [['' for _ in range(C)] for _ in range(R)] for i, tmp in enumerate(c): for j in range(C): maze[i][j] = tmp[j] ans = bfs(maze, R, C, sy, sx, gy, gx) return ans R , C = [int(i) for i in input().split()] sy , sx = [int(i) for i in input().split()] gy , gx = [int(i) for i in input().split()] c = [input() for _ in range(R)] print(C_BFS(R, C, sy, sx, gy, gx, c))
