Pythonで蟻本2-1 - DFS，BFS

蟻本2-1はDFS，BFSです．探索範囲を図（グラフとか）でイメージすると良いです．

背景：蟻本をやります - 競プロはじめました
テキスト：

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

DFS

部分和問題

【入力1】
4
1 2 4 7
13
【出力1】
Yes (13 = 7 + 4 + 2)

---

【入力2】
4
1 2 4 7
15
【出力2】
No

【コード】

def dfs(i, sum):
  ans  # 追加
  if i == n:
    return sum == k
  if dfs(i + 1, sum):
    return True
  if dfs(i + 1, sum + a[i]):
    ans.append(a[i])  # 追加
    return True
  return False

n = int(input())
a = list(map(int, input().split()))
k = int(input())

ans = []  # 追加
if dfs(0, 0):
  print('Yes ({} = {})'.format(k, ' + '.join(map(str, ans))))
else:
  print('No')

【ポイント】
再帰関数は，一番深いところから考える（プログラムが実行される順に考える）のがポイントです（ぷよぷよの連鎖みたいですね）．

• 関数dfsでは，ifが上から順に試される．
• 関数dfsは，いずれかのifでTrueとなれば，Trueを返して終了する．全てのifでFalseならFalseを返して終了する．
• 以上を踏まえると，dfs(0, 0)が実行されたとき，次の2つの場合が考えられる．
  
  1. 最深部(i==n) でsum==kとなる場合：dfs(n, sum)==Trueとなる．よって，nより浅いdfs(i, sum)ではif dfs()==Trueとなるため，dfs(0, 0)==Trueとなる．
  2. 最深部(i==n) でsum!=kとなる場合：dfs(n, sum)==Falseとなる．よって，nより浅いdfs(i, sum)ではif dfs()==Falseとなるため，dfsの最後のreturn Falseが実行される．結果，dfs(0, 0)==Falseとなる．
• 関数はreturnで終了するため，sum==kとなるものが「1つ」見つかった時点でdfs(0, 0)は終了する．

Lake Counting

「水溜りを全部消すのに必要な操作回数＝水溜りの個数」と考えるのですね．面白いです．
【入力（作るの面倒だった．．．）】
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
【出力】
3
【コード】

n, m = map(int, input().split())
field = [list(input()) for i in range(n)]

neighbor = [-1, 0, 1]  # range(-1, 2)
def dfs(x, y):
  field[x][y] = '.'
  for dx in neighbor:
    for dy in neighbor:
      nx = x + dx
      ny = y + dy
      if (0 <= nx and nx < n
          and 0 <= ny and ny < m
          and field[nx][ny] == 'W'):
        dfs(nx, ny)
  return

res = 0
for i in range(n):
  for j in range(m):
    if field[i][j] == 'W':
      dfs(i, j)
      res += 1

print(res)

【ポイント】

• dfs(x,y)は，①(x,y)を'.'に置き換え，②(x,y)の8近傍にある'W'でdfs(x,y)を実行する関数．つまり，(x,y)から8近傍づたいに到達できる全ての'W'を'.'で置き換える．
• 全てのfield[i][j]を探索して'W'があればdfs(i,j)を実行し，その実行回数をresで数える．

最後にprint(field)すると，全て'.'に置き換わっているのが確認できます．

BFS

迷路の最短路

Pythonでキューを使う方法をはじめ蟻本をPythonで (初級編) - Qiitaを参考にしました．
【入力】
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
【出力】
22
【コード】

from collections import deque

n, m = map(int, input().split())
maze = [list(input()) for _ in range(n)]

# スタート・ゴールの座標
for i in range(n):
  for j in range(m):
    if maze[i][j] == 'S':
      sx, sy = i, j
    if  maze[i][j] == 'G':
      gx, gy = i, j

# 4方向の移動ベクトル：(dx[i], dy[i])
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

def bfs():
  # 各座標の距離をinfで初期化(未探索のフラグ)
  d = [[float('inf')] * m for _ in range(n)]
  
  # 初期化(スタート地点をキューに入れ，距離ゼロとする)
  que = deque([])
  que.append([sx, sy])
  d[sx][sy] = 0
  
  # キューが空になるまでループ
  while que:
    # キューの先頭を取り出す
    px, py = que.popleft()
    # ゴールなら探索終了
    if px == gx and py == gy:
      break
    # 取り出した座標から移動できる4方向を探索する
    for i in range(4):
      nx, ny = px + dx[i], py + dy[i]
      if (0 <= nx and nx < n
          and 0 <= ny and ny < m
          and maze[nx][ny] != '#'
          and d[nx][ny] == float('inf')):
        que.append([nx, ny])
        d[nx][ny] = d[px][py] + 1
  # ゴールの距離を返す
  return d[gx][gy]

print(bfs())

【ポイント】

• x, y座標を分解して扱うとわかりやすい．たぶん，バグも出にくくなる．
• ①スタートから1ステップで行ける点を次の探索対象にする，②新たな探索対象から，1ステップで行ける点を次の探索対象にする，．．．を繰り返す．つまり，nステップ目の探索対象は，スタートからnステップで行ける全ての点となる．

【メモ】

• スタートやゴールのインデックスを取得する，もっとスマートな方法はない？