FUNCoder-第10回活動
第10回活動 2024/07/10 18:15~19:45 @593教室
トップページはこちら: FUNCoder
#2024-07-10 #グラフ理論 #BFS
/icons/hr.icon
はじめに
本日は前回の FUNCoder-第9回活動 の続きでグラフ理論について学習していきます。
前回は DFS（深さ優先探索）について学習しましたが、今回は BFS（幅優先探索）について学習していきます。
BFS 個人的には DFS よりも直感的なのでわかりやすいかと思います。頑張りましょう。
また、前回同様自分には早いと思った学生は FUNCoder-第4回活動, FUNCoder-第5回活動, アルゴ式 等で基本的な競プロの問題を解いてみることをお勧めします。
本日行う難易度は前回と同様か、それより少し優しめの難易度となっています。
頑張りましょう。
バチャのリンクはこちらになります
https://kenkoooo.com/atcoder/#/contest/show/6d044875-6f29-4bd9-b407-be3f60e90e15
/icons/hr.icon
まずはこちらの問題を元に解説していきます
1. ABC007 🧪C - 幅優先探索
可視化出来る ツール を作ったので遊んでみてください
1. 入力を受け取り、0-indexed に変換する
code:1.py
R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
# 1-indexed から 0-indexed に変換する
sy -= 1
sx -= 1
gy -= 1
gx -= 1
# グリッドの入力
grid = input() for _ in range(R)
2. 必要なものを諸々準備する
code:2.py
import deque # queue を使えるように import する
q = deque() # キューの作成
q.append((sy, sx)) # 始点座標を queue に push する
# distij := i 行 j 列目の距離 （初期値は -1 にしておく）
dist = [-1*C for _ in range(R)]
distsysx = 0 # スタート地点は距離が 0
d = ((0, 1), (0, -1), (1, 0), (-1, 0)) # 今いる地点からの上下左右４方向に対する変化量
3. BFS を行う
while q と while len(q) > 0 は同じ意味です
code:3.py
while q: # queue の中身が空になるまで無限ループを行う
now_y, now_x = q.popleft() # 一番最後に入れたものを pop する（y座標, x座標）
for dy, dx in d: # 上下左右4つの移動方向を1つずつみていく
next_y = now_y + dy # 移動した先の y 座標
next_x = now_x + dx # 移動した先の x 座標
# 配列外参照チェックをする
if not (0 <= next_y < R and 0 <= next_x < C):
continue
# 既に訪れている場所であればもう一度探索を行わない
if distnext_ynext_x != -1:
continue
# 移動した先が # （壁） であれば、距離の更新を行うことができないので continue する
if gridnext_ynext_x == '#':
continue
# （移動先の距離） = （移動前の距離） + 1
distnext_ynext_x = distnow_ynow_x + 1
# 今いる地点を queue に push し、そこからさらに探索を行えるようにする
q.append((next_y, next_x))
コード全容
code:Python
# queue を使えるように import する
from collections import deque
R, C = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
# 0-indexed は lambda 式を使用することをオススメします
# sy, sx = map(lambda x: int(x) - 1, input().split())
# gy, gx = map(lambda x: int(x) - 1, input().split())
# 1-indexed から 0-indexed に変換する
sy -= 1
sx -= 1
gy -= 1
gx -= 1
# グリッドの入力
grid = input() for _ in range(R)
q = deque() # キューの作成
q.append((sy, sx)) # 始点座標を queue に push する
# distij := i 行 j 列目の距離 （初期値は -1 にしておく）
dist = [-1*C for _ in range(R)]
distsysx = 0 # スタート地点は距離が 0
d = ((0, 1), (0, -1), (1, 0), (-1, 0)) # 今いる地点からの上下左右４方向に対する変化量
while q: # queue の中身が空になるまで無限ループを行う
now_y, now_x = q.popleft() # 一番最後に入れたものを pop する（y座標, x座標）
for dy, dx in d: # 上下左右4つの移動方向を1つずつみていく
next_y = now_y + dy # 移動した先の y 座標
next_x = now_x + dx # 移動した先の x 座標
# 配列外参照チェックをする
if not (0 <= next_y < R and 0 <= next_x < C):
continue
# 既に訪れている場所であればもう一度探索を行わない
if distnext_ynext_x != -1:
continue
# 移動した先が # （壁） であれば、距離の更新を行うことができないので continue する
if gridnext_ynext_x == '#':
continue
# （移動先の距離） = （移動前の距離） + 1
distnext_ynext_x = distnow_ynow_x + 1
# 今いる地点を queue に push し、そこからさらに探索を行えるようにする
q.append((next_y, next_x))
# 全地点の距離の確認（debug）
#print(*dist, sep='\n')
# 終点座標の距離を出力して終了
print(distgygx)
/icons/hr.icon
2. ABC016 🧪C - 友達の友達
これは先ほどの迷路の幅優先探索ができれば解けて欲しいなぁ、と思う問題です。
下にヒントを貼ります
ヒント
当然 BFS の練習なので BFS を使用することで解くことが出来ます
※ BFS を使用しなくても解く別解は多数存在します
制約の$ N, Mがかなり小さいのでとんでも解法（$ O(N!), O(N^N)）などを考えない限りは何をしても基本余裕で間に合いそうですね。
BFS の計算量は$ O(N + M)です
この問題は「友達の友達」の人数を各人に対して数える問題です
「ユーザ」を頂点とみなして、あるユーザ$ Aとあるユーザ$ Bが繋がっている時、頂点$ Aから$ Bに辺を貼ることでグラフ理論の問題に落とし込むことができます
「友達の友達」を BFS の各頂点間の距離として考えた時、距離がどのようになっていれば「友達の友達」と定義することができますか？
解答例 (Python)
code:Python
from collections import deque
# 入力を受け取る
N, M = map(int, input().split())
# グラフのリストを作る
g = [[] for _ in range(N)]
for _ in range(M):
A, B = map(lambda x: int(x) - 1, input().split())
gA.append(B)
gB.append(A)
# 各頂点から bfs をする、ということを全探索する
for i in range(N):
q = deque()
q.append(i)
dist = -1*N
disti = 0
while q:
now = q.popleft()
for nxt in gnow:
if distnxt != -1:
continue
distnxt = distnow + 1
q.append(nxt)
# 「友達の友達」、つまり距離が 2 の頂点の数が答えになる
ans = 0
for i in range(N):
if disti == 2:
ans += 1
print(ans)
/icons/hr.icon
3. ABC264-D "redocta".swap(i,i+1)
次の問題は少し工夫が必要です。
ぱっと見はほとんど BFS に見えないかもしれませんが、BFS で解くことが出来ます。
はじめに
この問題は自分の想定では defaultdict ライブラリを使用します。前々から競プロでは最強のライブラリと定期的に言っていましたが、使用する場面があまりなかったので今回頑張って使用してみようという旨です。なのでまずは BFS よりも前に defaultdict について学習します。
defaultdict にはざっと目を通した感じ、こちらの記事 が個人的にはとりあえず良いのかなと感じました
defaultdictの公式リファレンスは こちら です
以下は defaultdict の使い方がなんとなくわかった程で進んでいきます
ヒント
以下、入力例 1 を元に考えます
catredo を距離$ 0スタートの文字列としてここから$ 1回 swap することで作れる文字列を考えます
この問題では隣り合う$ 2文字しか入れ替えられないので、以下の$ 6通りになります
actredo
ctaredo
cartedo
caterdo
catrdeo
catreod
これは for 文を用いれば簡単に作れますよね？（str 型では文字列の置換ができないので list に変換しましょう）
この上記の$ 6個の文字列を距離$ 1の文字列とします
すると勘の良い方は気づいて来るかもしれません、文字列の swap 回数を距離とみなして BFS を行います
これは defaultdict を用いて、key を出来上がった文字列、value を swap 回数とすることで実現することが出来ます。
求める答えは d["atcoder"] となるわけです
解答例 (Python)
code:Python
from collections import deque, defaultdict
S = list(input())
# デフォルトだと初期値が 0 なのでこれを bfs のおきまり -1 にします
d = defaultdict(lambda : -1)
# list 型で defaultdict の key を持つことは出来ないので、7 文字を繋げて str 型にします
d"".join(S) = 0
q = deque()
q.append("".join(S))
while q:
now = list(q.popleft())
for i in range(6):
nxt = i for i in now
# i 文字目と i+1 文字目をスワップする
nxti, nxti + 1 = nxti + 1, nxti
if d"".join(nxt) == -1:
d"".join(nxt) = d"".join(now) + 1
q.append("".join(nxt))
print(d"atcoder")
余談
実はこの解法を用いると、先週の ABC361-D を BFS で解くことが出来ます。
水 diff でレベルが高いですが、やっていることは上記の問題を少し応用しただけになるのでぜひ挑戦してみてください。
/icons/hr.icon
4. E - チーズ (Cheese)
この問題に解ければ BFS の問題の基礎はほぼ理解できてると思って良いと思います。
これは 第 10 回 JOI 予選の問題になります。つまり、高校生以下が対象となるコンテストの予選問題です。
レベル高いですね...
ヒントを載せます
ヒント
要は連番となっている場所を行き続けて最終的な距離を出力する問題です
スタート地点だけ S となっていては少し処理が if 文等で面倒くなるので、 S は 0 に置き換えましょう
チーズ$ 0 \: (S)からチーズ$ 1の距離は求められますか？
これは前の問題を自力で理解できているのであれば、時間はかかれど簡単に求められるはずです
ではチーズ$ 1からチーズ$ 2の距離は求められますか？これも上記同様にできますよね
ということはこれを for 文で回して、「チーズ$ iからチーズ$ i + 1の距離を求める」ということをしてあげればその総和が答えになりますよね？
入力例$ 2ならば、チーズ$ 0からチーズ$ 1の距離が$ 4、チーズ$ 1からチーズ$ 2までの距離が$ 8なのでこの和を取って、$ 4 + 8 = 12といった具合に求められます。
解答例 (Python)
code:Python
from collections import deque
H, W, cheese = map(int, input().split())
S = list(input()) for _ in range(H)
# placei := チーズ i のある座標
place = [0*2 for _ in range(cheese + 1)]
# スタート地点 S とチーズの番号を探索する
for i in range(H):
for j in range(W):
# S の場所を探す
if Sij == "S":
sy, sx = i, j
Sij = "0" # 0 の方が都合が良いので S から変更する
# 「.」か「X」以外であればチーズの場所になる
if Sij == ".":
continue
if Sij == "X":
continue
# 何番のチーズなのかを int に変換して座標を特定する
cheese_num = int(Sij)
placecheese_num = i, j
# 全てのチーズの場所の出力（デバッグ）
# print(*place, sep="\n")
d = ((1, 0), (-1, 0), (0, 1), (0, -1))
dist = 0*cheese # disti := チーズ i からチーズ i+1 までの距離
# チーズ i からチーズ i+1 までの距離を BFS で求める (0 ≤ i < cheese)
for i in range(cheese):
sy, sx = placei # チーズ i の座標
q = deque()
q.append((sy, sx))
cost = [-1*W for _ in range(H)]
costsysx = 0
while q:
vy, vx = q.popleft()
for dy, dx in d:
ny = vy + dy
nx = vx + dx
if not (0 <= ny < H and 0 <= nx < W):
continue
if Snynx == "X":
continue
if costnynx != -1:
continue
costnynx = costvyvx + 1
q.append((ny, nx))
gy, gx = placei + 1 # チーズ i+1 の座標
disti = costgygx
# 各チーズ間の距離が dist に格納されているのでそれの sum が答えになる
print(sum(dist))
/icons/hr.icon
5. E - イルミネーション (Illumination)
これは本当に早く終わって暇になってしまった方向けの問題です。
ヒントも解答例も載せないので頑張って挑戦してみましょう。
/icons/hr.icon
最後に
$ 2回にわたって、グラフ理論の基礎である BFS, DFS を学習しました。
本日やった BFS は 精選 100 問 から問題を抜粋してるものが多くあります。
また、ここにある問題は昔 ブログ に解答を載せたので意欲のある方はぜひ参考にしてみてください。