グラフの s,t パス 2

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

問題概要

🎯 やること

• 無向グラフが与えられる
• 始点 s
• 終点 t
• s から t までのすべてのパスを出力する

🧩 パスとは？

• 同じ頂点を2回通らない
• 同じ辺も通らない
• つまり「訪問済み禁止」

📥 入力

• n：頂点数（3〜10）
• s：始点
• t：終点
• 各頂点の隣接リスト

📤 出力

• パスの総数
• s → t のすべてのパス
  • 左端は必ず s
  • 右端は必ず t
  • 順番は自由
    
    
    

入力例:

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

出力例:

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

✅OK例：

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

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

rl.on('close', () => {
    const [n, s, t] = 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 visit = Array(n+1).fill(false);
    const paths = [];
    
    function dfs(v, path) {
        visit[v] = true;
        
        for (const next of graph[v-1]) {
            if (!visit[next]) {
                path.push(next); // パスに追加
                
                if (next === t) {
                    paths.push([...path]); // コピーした保存
                } else {
                    dfs(next, path); // 再帰
                }
                
                path.pop(); // パスから削除
            }
        }
        
        visit[v] = false; // 次の分岐を調べるため、前の未訪問の状態に戻す
    }
    
    // スタートを含める
    dfs(s, [s]);
    console.log(paths.length);
    paths.forEach(p => console.log(p.join(' ')));
});

🔍 コードの流れ

① 入力を受け取る

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

② 準備

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

③ dfs 関数を定義
引数

• v：現在いる頂点
• path：今まで通った頂点の配列

目的：

「今 v にいて、t まで到達するすべてのパスを探す」

④ 再帰の処理

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

• visit[v] = true

2️⃣ 隣接頂点を順番に見る

• まだ訪問していない頂点だけ進む

3️⃣ 次の頂点を path に追加

• path.push(next)

4️⃣ t に到達した場合

• paths.push([...path])
• 今のパスをコピーして保存

5️⃣ まだ t でない場合

• dfs(next, path) を呼び出す
• さらに深く探索

6️⃣ 戻るとき

• path.pop()（追加した頂点を削除）
• 分岐を元に戻す

7️⃣ 探索終了時

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

⑤ 探索開始

• dfs(s, [s])
• 始点 s から探索スタート

⑥ 出力

• 1行目：パスの総数
• 2行目以降：各パスを出力

📝まとめ

🌳 処理のイメージ

s
├─ A
│ ├─ B
│ │ └─ t ← 保存
│ └─ t ← 保存
└─ C
└─ t ← 保存

全部の枝を深く辿る

〇 DFS

• 訪問 → 再帰 → 戻す
• push → dfs → pop
• visit[v] = true→ 最後にfalse` に戻す

〇 なぜコピーが必要？

• 配列は共有渡し
• [...path] で保存しないと全部同じになる