グラフのパス 2

今回は paiza の「グラフのパス 2」の問題に挑戦！

🧩 問題概要

🔹 グラフ

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

🔹 入力

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

🔹 やること

• 頂点 s から出発
• ちょうど k 回移動
• 条件を満たす すべてのパスを列挙

🔹 パスとは？

• 頂点の重複 ❌
• 辺の重複 ❌
• 一度通った頂点には戻れない

👉 「重複禁止の経路」

🔹 出力

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

入力例:

5 5 3
2
2 5
3
1 3 5
3
2 4 5
2
3 5
4
1 2 3 4

出力例:

4
5 1 2 3
5 2 3 4
5 3 2 1
5 4 3 2

✅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 = [];
    const visit = Array(n+1).fill(false);
    
    function dfs(v, path, k) {
        visit[v] = true;
        
        if (k === 0) {
            arr.push([...path]);
        } else {
            for (const next of graph[v-1]) {
                if (!visit[next]) {
                    path.push(next);
                    dfs(next, path, k-1);
                    path.pop();
                }
            }
        }
        visit[v] = false;
    }
    
    dfs(s, [s], k);
    console.log(arr.length);
    arr.forEach(a => console.log(a.join(' ')));
});

🔍 コードの流

① 入力を受け取る

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

② 準備

• arr：完成したパスを保存する配列
• visit：訪問済み管理用（頂点の重複を防ぐ）

③ dfs 関数を定義
引数

• v：現在いる頂点
• path：これまで通った頂点の配列
• k：残り移動回数

④ 再帰の処理

1️⃣ 今いる頂点を訪問済みにする

• visit[v] = true

2️⃣ k === 0 のとき

• ちょうど k 回移動完了
• path をコピーして arr に保存

3️⃣ k > 0 のとき

• 隣接頂点を順番に見る
• まだ訪問していない頂点だけ進む
  • path.push(next)
  • dfs(next, path, k-1)
  • path.pop()（元に戻す）

4️⃣ 探索終了時

• visit[v] = false
• 他のルートのために訪問状態を戻す

⑤ 探索開始

• dfs(s, [s], k) を呼び出す
• 始点 s から深さ k の全パスを探索

⑥ 出力

• 1行目：パスの総数
• 2行目以降：各パスをスペース区切りで出力

📝まとめ

重複禁止ルール付きで、深さ k まで全パターンを列挙するDFS