AIで解説 AtCoder攻略　DFS・BFS探索

DFS・BFS探索ページの位置づけ

項目	内容
必修度	必修
学習目安	入門〜標準
前提	隣接リスト・visited
対象問題	14問（推定値あり14問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	1
標準	0〜799	7
標準〜発展	800〜1199	1
発展	1200以上	5
未算出	—	0

最短距離ではなく「どこまで到達できるか」「何個の頂点を訪れたか」を調べるための探索ページです。訪問済み管理と隣接リストの作り方を同じ型で練習します。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

DFS・BFS探索の見分け方

到達できるか、連結しているかだけを答える
各頂点を一度ずつ訪問すればよい
距離の最小性より訪問順や依存関係が重要

DFS・BFS探索の実装前チェック

訪問済みを先に付けて無限ループを防ぐ
無向辺は両方向へ追加する
最短距離が必要ならshortest-pathへ移す

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC293 C Make Takahashi Happy （公式解説）を解きます。右と下への経路をDFSで列挙し、同じ数を2回通る経路だけを除きます。戻るときに集合から値を外すのがポイントです。

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
answer = 0

def dfs(r, c, seen):
    global answer
    value = A[r][c]
    if value in seen:
        return
    seen.add(value)
    if r == H - 1 and c == W - 1:
        answer += 1
    else:
        if r + 1 < H:
            dfs(r + 1, c, seen)
        if c + 1 < W:
            dfs(r, c + 1, seen)
    seen.remove(value)

dfs(0, 0, set())
print(answer)

経路数をPとするとO(P・HW)です。H,Wが小さい制約なので、全経路を調べるDFSが使えます。

DFS・BFS探索の学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC423 B Locked Rooms	公式解説	公式Editorialの方針を locked rooms bfs として整理する。	-514
ABC244 C Yamanote Line Game	公式解説	未使用番号集合を管理し、相手の発言後に最小未使用番号を返す対話戦略を実装する。	46
ABC291 C LRUD Instructions 2	公式解説	移動した座標を集合に記録し、再訪があるか判定する。	97
ABC293 C Make Takahashi Happy	公式解説	右下までの各経路をDFSし、通過値の積がすべて異なる経路数を数える。	431
ABC226 C Martial artist	公式解説	最後の技に必要な前提技を再帰的にたどり、必要な時間を一度だけ合計する。	539

次に解く

問題	公式解説	出題意図	difficulty
ABC378 D G. Count Simple Paths	公式解説	訪問済み頂点を管理するDFSで単純路を列挙し、上限まで個数を数える。	587
ABC233 C Product	公式解説	各リストから1個ずつ選ぶ積をDFSで生成し、目標Xに一致する選び方を数える。	604
ABC420 E H. Reachability Query	公式解説	公式Editorialの方針を reachability bitset として整理する。	790
ABC351 D G. Grid and Magnet	公式解説	Official editorial intent is classified as grid magnet components.	974
ABC292 E H. Transitivity	公式解説	各頂点から到達できる頂点を探索し、推移閉包の辺数を数える。	1272

挑戦問題

問題	公式解説	出題意図	difficulty
ABC305 F I. Dungeon Explore	公式解説	Explore unknown corridors with DFS while issuing movement/backtrack commands.	1420
ABC446 F I. Reachable Set 2	公式解説	Compute the transitive reachable set with graph search and bitset unions.	1543
ABC345 F I. Many Lamps	公式解説	Official editorial intent is classified as graph parity dfs.	2157
ABC219 F I. Cleaning Robot	公式解説	移動列の1周期の軌跡と周期変位を用い、重複する周期位置を正規化して訪問マス数を数える。	2542