【G検定対策】探索木の数え方
司会者: 「本日は『幅優先探索と深さ優先探索の数え方』にフォーカスします！特にG検定対策として、数え方をどう身につけるか、お二人の専門家に教えてもらいます。それでは、幅優先さんと深さ優先さん、よろしく！」
1. 幅優先探索（BFS）の数え方
幅優先探索: 「どうも、幅優先探索です！俺の数え方は超シンプル。『近場から順番に』進むだけ！とりあえず近いところを全員探してから、次にちょっと遠いところへ。」
お題：階段登りゲーム
ルール: 「まずは1段目に全員が立つ。次に、2段目、3段目と順番に上がっていく！」
数え方: 「ある地点にたどり着くまで何段目で到達するか？それが俺のステップ数だ！」
ポイント:
最初に出発地点（根ノード）を数える。
そこから広がるノードを順にレベルごとに数える。
**目標地点が出てきたらストップ！それまでのステップが答えだ！」
オチ: 「俺は『階層ごとに数える』探査の几帳面お兄さんさ！」
2. 深さ優先探索（DFS）の数え方
深さ優先探索: 「オッス！俺は深さ優先探索！とにかく『進めるだけ進む』。行き止まりに着いたら戻って別の道を探すタイプさ！」
お題：迷路の一本道
ルール: 「まずは一本道をひたすら歩く。途中で袋小路に入ったら引き返す。でも絶対諦めないで別ルートを探る！」
数え方: 「道を進むたびに『何歩目か』を記録して、ゴールしたらその数字を数えるだけ。」
ポイント:
スタート地点から一直線に進む。
ゴールにたどり着いたらステップ数をカウント。
行き止まりに戻るときはカウントせず、別ルートで再挑戦。
オチ: 「俺は『一本筋』の探査。歩きっぱなしで疲れるけど、ゴールの達成感は格別だぜ！」
3. 幅優先と深さ優先を区別する覚え方
お題：フードデリバリー
幅優先探索: 「俺はピザ配達。家が近い順に配達する。時間効率重視！」
深さ優先探索: 「俺は探検家。とりあえず一本の道を極めて、地の果てまで届けるスタイル！」
観客: 「どっちも目的が違うから便利そう！」
オチ: 「俺たち、配達界の『効率派＆冒険派』だな！」
4. G検定対策：数え方のコツ
幅優先探索（BFS）の数え方の手順
レベルを意識！
出発点を「0ステップ」として数え始める。
最初のレベル（直近）は「1ステップ」。
その次のレベル（さらに遠い場所）は「2ステップ」。
階層を進むたびにステップを増やす！
子ノードを処理したら次の階層に進む。
「ここだ！」とゴールに到達したら、そのレベルが答え。
深さ優先探索（DFS）の数え方の手順
ゴールを目指してひたすら進む！
出発点を「0」として、進むたびに「+1」。
行き止まりに戻るときはステップをカウントせず次のルート。
探索が完了したら最小のステップ数をチェック！
複数ルートがある場合、一番少ないステップ数が答え。
オチ: 「BFSは『階層を意識して数える』。DFSは『一歩ずつ歩みながらゴールを探す』だ！」
5. キャッチコピーで覚える！
幅優先探索: 「横一列ずつ広がる波、レベルがカギ！」
深さ優先探索: 「一本道を突き進む探検家、歩数に注目！」
G検定攻略: 「数え方を意識すればステップ問題も楽勝！」
6. 練習問題を楽しむ方法
お題：階段競争
幅優先探索: 「近場から一段ずつ広がっていく階段の旅！」
深さ優先探索: 「まずはとにかく一直線に駆け上がる階段の旅！」
司会者: 「幅優先探索と深さ優先探索の数え方をマスターしたら、次回は実際にG検定の過去問に挑戦してみましょう！」
観客: 「ブラボー！」 🎉