パスの経由地 2

今回は paiza の「パスの経由地 2」の問題に挑戦！

問題概要

🎯 やること

• 無向グラフが与えられる
• 始点 s
• 終点 t
• 経由必須の頂点 p

s から t までのパスのうち、p を通るものをすべて出力する

🧩パスの定義

• 同じ頂点を2回通らない
• 同じ辺も通らない
• 左端は必ず s
• 右端は必ず t

📥 入力

• n：頂点数
• s：始点
• t：終点
• p：必ず経由する頂点（s,t ではない）
• 各頂点の隣接リスト

📤 出力

• 条件を満たすパスの総数
• そのパスをすべて出力
  • 順番は自由
  • 各行は「頂点番号をスペース区切り」

入力例：

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

出力例：

5
1 2 3 4
1 2 3 5 4
1 2 5 3 4
1 5 2 3 4
1 5 3 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, p] = 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) {
                    if (path.includes(p)) 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(' ')));
});

🔍コードの流れ

① 入力を受け取る

• n, s, t, p を取得
  • s：始点
  • t：終点
  • p：必ず経由しなければならない頂点
• 隣接リスト graph を作成

② 準備

• visit：訪問済み管理
• paths：条件を満たすパスを保存

③ dfs 関数を定義
引数

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

目的：
s から t までのパスのうち、p を含むものを探す

④ dfs の処理

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

• visit[v] = true;

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

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

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

• path.push(next);

4️⃣ next が t の場合

• ゴールに到達
• ここで条件チェック
• if (path.includes(p))
• p を含んでいれば保存
• 含まなければ捨てる

5️⃣ next が t でない場合

• dfs(next, path) でさらに探索

6️⃣ 戻るとき

• path.pop();
• 追加した頂点を削除
• 別ルートへ進めるようにする

7️⃣ 探索終了時

• visit[v] = false;
• 他の分岐のために未訪問に戻す

⑤ 探索開始

• dfs(s, [s]);
• s からスタート

⑥ 出力

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

📝まとめ

前回： s → t のすべてのパス

今回：s → t のうち「p を含むパスだけ」

違いはここだけ：

if (path.includes(p)) paths.push([...path]);