DFS（深さ優先探索）の考え方と実装

DFSは行ける所まで深く探索し行き止まりで戻る探索

DFSで必ず考える3点セット

DFSを書く前に、必ず次を決める：

1.今いる場所（状態）

• 頂点番号、マス座標 (x, y) など

2.行っていい遷移

• 隣接頂点
• 上下左右
• 条件を満たす次の状態

3.戻ってはいけない条件

• visited 配列
• 親 p（木の場合）

DFSは「状態遷移の全列挙」 と考え応用が効く。

DFSでよくやること

• 到達可能か調べる
• 連結成分の個数を数える
• 条件を満たす経路が存在するか
• 木での部分木集計（サイズ、深さ、距離）

DFSの実装方法

① 基本形（visitedあり・一般グラフ）

vector<vector<int>> G;
vector<bool> visited;

void dfs(int v) {
    visited[v] = true;        // 入った瞬間に訪問済みにする
    for (int to : G[v]) {
        if (visited[to]) continue;
        dfs(to);
    }
}

使いどころ

• 連結判定
• グラフ探索全般
• サイクル検出（無向）

② 木DFS（親を持つ・visited不要）

void dfs(int v, int p) {
    for (int to : G[v]) {
        if (to == p) continue;
        dfs(to, v);
    }
}

使いどころ

• 木（N−1辺）
• 部分木サイズ
• 木DP

③ 情報を引数で持たせるDFS

void dfs(int v, int dist) {
    visited[v] = true;
    ans = max(ans, dist);
    for (int to : G[v]) {
        if (!visited[to]) {
            dfs(to, dist + 1);
        }
    }
}

ポイント

• 距離・深さ・スコアなどは引数で渡す
• グローバル変数で答えを更新することが多い

④ グリッドDFS（上下左右）

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int x, int y) {
    visited[x][y] = true;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];
        if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if (visited[nx][ny]) continue;
        if (S[nx][ny] == '#') continue;
        dfs(nx, ny);
    }
}

DFS実装の注意点

• visited は dfsに入った瞬間に立てる
• 再帰が深くなりすぎる場合（N≈2e5）は注意
• 0-index / 1-index のズレは事故りやすい

問題から「DFSを使う」と判断する方法

DFSを疑うキーワード

問題文に次があったらDFS候補：

• 「到達できるか」
• 「連結」
• 「すべて訪れる」
• 「経路が存在するか」
• 「同じグループ」
• 「移動できるマス」

問題構造での判断基準

① グラフ or マス移動？

• 頂点と辺 → DFS
• マス＋上下左右 → DFS

② 「全部調べたい」？

• Yes → DFS/BFS
• 最短距離 → BFS
• 全列挙 → DFS

③ Nが小さく「試せそう」？

• 組み合わせ・分岐探索 → DFS

DFS / BFS / DP の見分け方（簡易）

状況	選択
連結・到達	DFS
最短距離	BFS
数え上げ・最大値	DFS
重複部分問題	DP

まとめ

DFS は 状態を決めて、行ける所へ深く進み、visitedで戻りを防ぐ