グラフのウォーク 2

Posted at 2026-03-02

今回は paiza の「グラフのウォーク 2」の問題に挑戦！

🧩 問題概要

🔹 グラフについて

頂点は 1 ～ n
無向グラフ
自己ループなし
多重辺なし
隣接リスト形式で与えられる

🔹 入力

n：頂点数
s：始点
k：移動回数
各頂点の隣接頂点リスト

🔹 やること

頂点 s から
ちょうど k 回移動する
すべてのウォークを列挙する

🔹 ウォークとは？

頂点の重複 OK
辺の重複 OK
同じ場所を何回通ってもよい

👉 「制限なしで k 回動く全パターン」

🔹 出力

1行目：ウォークの総数 W
2行目以降：
- 各ウォークを1行ずつ出力
- 頂点数は k+1 個（s を含む）
- 順番は問わない

入力例：

出力例：

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [n, s, k] = lines[0].split(' ').map(Number);
    
    const graph = [];
    let idx = 1;
    for (let i = 0; i < n; i++) {
        const v = Number(lines[idx++])
        graph.push(lines[idx++].split(' ').map(Number));
    }
    
    const arr = [];
    
    function dfs(v, walk, k) {
        if (k === 0) {
            arr.push([...walk]);
        } else {
            for (const next of graph[v-1]) {
                walk.push(next);
                dfs(next, walk, k-1);
                walk.pop();
            }
        }
    }
    
    dfs(s, [s], k);
    console.log(arr.length);
    arr.forEach(a => console.log(a.join(' ')));
});

🔍コードの流れ

① 入力を受け取る

1行目から n, s, k を取得
その後の行から隣接リストを作る
graph[i] に「頂点 i+1 の隣接頂点配列」を入れる

② 結果を入れる配列を用意

arr を用意
ここに完成したウォークを全部保存する

③ dfs 関数を定義

引数：

v → 現在いる頂点
walk → 今まで通った頂点の配列
k → 残り移動回数

④ 再帰の処理

k === 0 のとき
→ 今の walk をコピーして arr に追加（参照を渡してしまうのを防ぐ）
k !== 0 のとき
→ 現在の頂点 v の隣接頂点をすべて試す
- walk に追加
- dfs(next, walk, k-1)
- 戻ってきたら pop() で元に戻す

⑤ 探索開始

dfs(s, [s], k) を呼ぶ
始点 s から、長さ k の全ウォークを探索

⑥ 出力

1行目：ウォークの総数 arr.length
2行目以降：各ウォークをスペース区切りで出力

🔁 再帰関数 `dfs` の役割

function dfs(v, walk, k)

これは

「今いる頂点 v から、あと k 回動くすべてのウォークを作る関数」

🔁 引数の意味

🔹 v
今いる頂点（現在地）

🔹 walk

これまで通った頂点の記録
（例：2 → 3 → 4 なら [2,3,4]）

🔹 k
残り移動回数
「あと何回動けるか」

🔁 処理の流れ

① 終了条件（ベースケース）

if (k === 0)

もう動かない
今の walk が完成形
それを保存する

👉 「k 回ちゃんと動いた」ということ

② まだ動けるとき

for (const next of graph[v-1])

今いる頂点 v の隣接頂点を全部試す

やっていることは3ステップ

① walk.push(next)
→ 次の頂点へ進む

② dfs(next, walk, k-1)
→ 1回動いたので、残りを減らして再帰

③ walk.pop()
→ 戻る

🔄 `walk.pop()`の役割

「試して戻す」動き。

追加 → 再帰 → 削除

これがないと、
別ルートに進んだときに前の値が残ってしまう。

📝まとめ

① ウォークとパスの違い

パス → 重複禁止 → visit 必要
ウォーク → 重複OK → visit 不要

👉今回は visit 不要

② 再帰の基本形

追加 → 再帰 → 削除

③ 深さ制御の考え方

「k回動く」＝「再帰をk回進める」
k をカウントダウンする

④ なぜコピーが必要か

配列は参照型
そのまま保存すると後で全部書き換わる
[...walk] で状態を固定する

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up