1. 目的
初中級者が解くべき過去問精選 100 問をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。
本記事は「028 - 033 幅優先探索」です。
2. 総括
DFS ができればBFSはほぼ同じです。
違いはdeque()からポップする箇所でDFSではpop()を、BFSではpopleft()を使います。
3. 本編
028 - 033 幅優先探索
028. ALDS_11_C - 幅優先探索
回答
from collections import deque
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n):
i, num, *nodes = map(int, input().split()) # *で余分を回収
graph[i] = nodes # 有向グラフ
visited = [-1] * (n+1)
q = deque()
q.append(1)
visited[1] = 0
while q:
node = q.popleft()
for next in graph[node]:
if visited[next] != -1:
continue
q.append(next)
visited[next] = visited[node] + 1
for i, num in enumerate(visited[1:]):
print(i+1, num)
これは基礎問題。
ここで自分の型を作っておけば、あとは少しいじるだけで他の問題を解くことができると思われます。
BFS の流れをざっくり示すと、
1. visited で探索先の記録ようのリストをつくる
2. deque() をとりあえず準備して、初期値をいれる
3. deque() が空になるまでwhileを回す
4. popleft()で先入れ先出しで値を取り出す
5. 取り出した値からgraphを調べて行先を調べる
6. 行先が探索済みか否かを判定
7. 探索してない場合はappend してvisited を更新
です。
029. AtCoder Beginner Contest 007 C - 幅優先探索
回答
from collections import deque
R, C = map(int, input().split())
sy, sx = map(int, input().split())
sy -= 1 # 0インデックスに修正
sx -= 1
gy, gx = map(int, input().split())
gy -= 1 # 0インデックスに修正
gx -= 1
grid = [list(input()) for _ in range(R)]
visited = [[-1] * C for _ in range(R)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque()
q.append((sy, sx))
visited[sy][sx] = 0
while q:
start_y, start_x = q.popleft()
for dy, dx in moves:
moved_y = start_y + dy
moved_x = start_x + dx
if grid[moved_y][moved_x] == '#':
continue
if visited[moved_y][moved_x] != -1:
continue
visited[moved_y][moved_x] = visited[start_y][start_x] + 1
q.append((moved_y, moved_x))
print(visited[gy][gx])
これは典型中の典型です。
とりあえず覚える、です。
030. JOI 2011 予選 5 - チーズ
回答
from collections import deque
def bfs(start_y, start_x, target_cheese, H, W, grid):
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque()
q.append((start_y, start_x))
visited[start_y][start_x] = 0
while q:
y, x = q.popleft()
for dy, dx in moves:
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H - 1 < moved_y or moved_x < 0 or W -1 < moved_x:
continue
if grid[moved_y][moved_x] == 'X':
continue
if visited[moved_y][moved_x] != -1:
continue
if grid[moved_y][moved_x] == target_cheese:
visited[moved_y][moved_x] = visited[y][x] + 1
return visited[moved_y][moved_x]
visited[moved_y][moved_x] = visited[y][x] + 1
q.append((moved_y, moved_x))
if __name__ == "__main__":
H, W, N = map(int, input().split())
grid = [list(input()) for _ in range(H)] # Sは巣でスタート、数字はチーズの硬さ、Xは障害物、.は空き地
# ネズミは数字の順番にチーズを食べる
# 各数字から次の数字へのBFSを考える
# スタートと各数字の位置を先に把握する
start_y, start_x = 0, 0
cheese = [(0, 0) for _ in range(10)] # 初期値を(0, 0)にしておく
count = 0 # countにチーズの数をいれておく
for row in range(H):
for col in range(W):
if grid[row][col] == '.' or grid[row][col] == 'X':
continue
elif grid[row][col] == 'S':
start_y, start_x = row, col
else:
grid[row][col] = int(grid[row][col]) # グリッドの中身を数字に変えておく
cheese[int(grid[row][col])] = (row, col)
count += 1
# ------- [すべての点を探索] ----------
target_cheese = 1
time_count = 0
while target_cheese <= count:
time_count += bfs(start_y, start_x, target_cheese, H, W, grid)
start_y, start_x = cheese[target_cheese]
target_cheese += 1
print(time_count)
やや実装が重いです。
問題文より、ネズミは数字の小さいチーズから大きいチーズへと順番に食べていきますので、各数字から次の数字へのBFSを行ってやればよさそうです。
なので、スタート位置とゴール位置が決まっているBFSを、チーズの数字の順番に設定してやり、
S→1のBFS、1→2のBFS、2→3のBFS ・・・と行っていき、合計の最短距離が答えとなります。
031. JOI 2012 予選 5 - イルミネーション
回答
# girdの上下左右に0ますを全て付け加えて、
# 座標(0,0)から行ける各0点が接する1の数を足しあげる
from collections import deque
# ---------- [建物がない場所が隣接している建物の数を数える] --------------
def check_walls(y, x, grid, W, H, even_moves, add_moves):
count = 0
if y % 2 == 0:
moves = even_moves
else:
moves = add_moves
for dy, dx in moves:
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H + 1 < moved_y or moved_x < 0 or W + 1 < moved_x:
continue
if grid[moved_y][moved_x] == 1:
count += 1
return count
if __name__ == "__main__":
# ---------- [入力受取] --------------
W, H = map(int, input().split())
grid = []
grid.append([0] * (W+2))
for _ in range(H):
temp = list(map(int, input().split()))
temp = [0] + temp + [0]
grid.append(temp)
grid.append([0] * (W+2))
visited = [[-1] * (W+2) for _ in range(H+2)]
answer_count = 0
# ---------- [偶数と奇数で動ける方向が異なる] --------------
even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] # 左上から時計回り
add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] # 左上から時計回り
# ---------- [初期値設定] --------------
q = deque()
q.append((0, 0)) # (0, 0)から行ける建物がない場所についてBFSを実施する
count = check_walls(0, 0, grid, W, H, even_moves, add_moves) # 隣接する建物数をカウント
visited[0][0] = count
answer_count += count
# ---------- [BFS開始] --------------
while q:
y, x = q.popleft()
if y % 2 == 0:
moves = even_moves
else:
moves = add_moves
for dy, dx in moves:
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H + 1 < moved_y or moved_x < 0 or W + 1 < moved_x:
continue
if grid[moved_y][moved_x] == 1:
continue
if visited[moved_y][moved_x] != -1:
continue
q.append((moved_y, moved_x))
count = check_walls(moved_y, moved_x, grid, W, H, even_moves, add_moves)
visited[moved_y][moved_x] = count
answer_count += count
print(answer_count)
多くの問題は碁盤目状をベースとしたものですが、本問題は1つのマスが6角形であり若干異なります。
しかし、考え方も解き方も大きくは変わらず、変更するところは、BFSの移動の座標の設定方法です。
具体的には、僕の場合movesで定義している部分です。
本問題ではy座標が偶数と奇数の場合で、各マスから動ける先が異なってきます。
したがってそれぞれ下記のように定義をしてやります
even_moves = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)] # 左上から時計回り
add_moves = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)] # 左上から時計回り
通常の碁盤目状であれば上下左右、または、上下左右+斜めの移動成分を下記のように定義しますので、ここだけが違います。
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 上下左右のみの場合
moves = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)] # 上下左右+斜めの場合
ここさえ押さえればあとは下記方針として解いていきます
1. 大きな方針は、「建物がない箇所」をBFSで探索し、各箇所で隣接する建物を数えてその合計が答え
2. そのために、まずはデフォルトで受け取るgridの上下左右に追加で「建物がない箇所」を追加する
3. gridの左上(0, 0)からBFSを実施
4. その際にvisitedに記録するのは通常の0, 1ではなく、隣接する建物の数
5. そのため隣接する建物の数を数えるための関数であるcheck_wallsを作成しておく
6. BFSを行うにあたってはyが偶数の場合と奇数の場合で動き方違うので注意する
7. BFSを一通りおこなって、check_wallsで返ってきた数を合計したものが答え
です。
032. AOJ 1166 - 迷図と命ず
回答
from collections import deque
def main(w, h):
tatebou = []
yokobou = [[0] * w]
for _ in range(h-1):
tate = [0] + list(map(int, input().split()))
yoko = list(map(int, input().split()))
tatebou.append(tate)
yokobou.append(yoko)
tate = [0] + list(map(int, input().split()))
tatebou.append(tate)
visited = [[0] * w for _ in range(h)]
moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque()
q.append((0, 0))
visited[0][0] = 1
while q:
y, x = q.popleft()
for dy, dx in moves:
moved_y = y + dy
moved_x = x + dx
if dy == 1 and dx == 0:
if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
continue
if visited[moved_y][moved_x] != 0:
continue
if yokobou[moved_y][moved_x] == 1: # 下に行くときは動く先が1のときだめ
continue
visited[moved_y][moved_x] = visited[y][x] + 1
q.append((moved_y, moved_x))
elif dy == -1 and dx == 0:
if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
continue
if visited[moved_y][moved_x] != 0:
continue
if yokobou[y][moved_x] == 1: # 上に行くときは自分が1のときだめ
continue
visited[moved_y][moved_x] = visited[y][x] + 1
q.append((moved_y, moved_x))
elif dy == 0 and dx == 1:
if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
continue
if visited[moved_y][moved_x] != 0:
continue
if tatebou[moved_y][moved_x] == 1: # 右に行くときは動く先が1のときだめ
continue
visited[moved_y][moved_x] = visited[y][x] + 1
q.append((moved_y, moved_x))
else: # dy == 0 and dx == -1
if moved_y < 0 or h-1 < moved_y or moved_x < 0 or w-1 < moved_x: # 迷路外
continue
if visited[moved_y][moved_x] != 0:
continue
if tatebou[moved_y][x] == 1: # 左に行くときは自分が1のときだめ
continue
visited[moved_y][moved_x] = visited[y][x] + 1
q.append((moved_y, moved_x))
return visited[h-1][w-1]
if __name__ == "__main__":
answer_list = []
while True:
w, h = map(int, input().split())
if w == 0 and h == 0:
break
answer = main(w, h)
answer_list.append(answer)
for answer in answer_list:
print(answer)
基本的に問題29とやることは同じです。
異なる点は、当たり判定です。問題29は「マスそれ自体に行けない」という当たり判定でしたので簡単ですが、この問題は、「マス」ではなく「壁」です。
なので、通常のBFSでは必要ない場合分けを行う必要があります。
具体的には、上下左右の動き方それぞれで、下記のように当たり判定を変える必要があります。
if dy == 1 and dx == 0:
if yokobou[moved_y][moved_x] == 1: # 下に行くときは動く先が1のときだめ
continue
elif dy == -1 and dx == 0:
if yokobou[y][moved_x] == 1: # 上に行くときは自分が1のときだめ
continue
elif dy == 0 and dx == 1:
if tatebou[moved_y][moved_x] == 1: # 右に行くときは動く先が1のときだめ
continue
else: # dy == 0 and dx == -1
if tatebou[moved_y][x] == 1: # 左に行くときは自分が1のときだめ
continue
この当たり判定以外は普通に書くだけです。
033. AtCoder Beginner Contest 088 D - Grid Repainting
回答
# 白だけ動いて(0,0)から(H-1, W-1)に行く
# その際にできるだけ黒を増やす
# 全体の白から最短距離を除いたものが答え
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)] # .は白、#は黒
visited = [[-1] * W for _ in range(H)]
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
q = deque()
q.append((0, 0))
visited[0][0] = 0
while q:
y, x = q.popleft()
for dy, dx in moves:
moved_y = y + dy
moved_x = x + dx
if moved_y < 0 or H-1 < moved_y or moved_x < 0 or W-1 < moved_x:
continue
if grid[moved_y][moved_x] == '#':
continue
if visited[moved_y][moved_x] != -1:
continue
visited[moved_y][moved_x] = visited[y][x] + 1
q.append((moved_y, moved_x))
min_route = visited[H-1][W-1]
if min_route == -1:
answer = -1
else:
total_white = 0
for row in grid:
total_white += row.count('.')
answer = total_white - min_route - 1
print(answer)
ほかの問題を解けたのであれば、これは結構簡単です。
問題をかみ砕いて解釈すると「できるだけ黒に塗って左上から右下に移動するときの黒に塗った数」が回答になります。
これをもう少し解きやすいように解釈すると「左上から右下に最短距離で移動したときに、その他通っていないところの数」となります。
これがわかれば、普通にBFSで最短距離を算定して、全体のから引けばよいとわかります。
なので、方針は
1. (0,0)スタート、(H-1, W-1)ゴールで最短距離min_routeを算出
2. 全体の白の数total_whiteを算出
3. total_whiteからmin_routeを引いたものが答え（min_routeはゼロスタートなので-1を追加でする）
です。