パスの通れない頂点

今回は paiza の「パスの通れない頂点」の問題に挑戦！

🧩 問題概要

〇 目的

• 無向グラフが与えられる
• 始点：s
• 終点：t
• 通ってはいけない頂点集合：S

S の頂点を一切通らない s→t の最短パスを求める

〇 グラフの条件

• 頂点番号：1 ～ n
• 無向グラフ
• 自己ループなし
• 多重辺なし
• 同じ頂点は2回通れない（パス）
• n ≤ 12（小さい）

〇 入力

① 1行目

• n：頂点数
• s：始点
• t：終点

② 2行目

• k：禁止頂点数

③ 3行目

• S：通ってはいけない頂点

④ 以降（各頂点ごと）

• v_i：隣接頂点数
• 隣接頂点リスト

〇 出力

条件を満たすパスがある場合：

• s から始まり
• t で終わり
• S を1つも含まない
• 頂点数が最小

→ 頂点番号をスペース区切りで出力

存在しない場合：
→ -1

入力例：

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

出力例：

-1

✅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 k = Number(lines[1]);
    const S = lines[2].split(' ').map(Number);
    const forbidden = new Set(S);
    
    const graph = [];
    
    let idx = 3;
    for (let i = 0; i < n; i++) {
        const v = Number(lines[idx++]);   // 頂点数（使わなくてもOK）
        graph.push(lines[idx++].split(' ').map(Number));
    }
    
    const visit = new Array(n + 1).fill(false);
    const arr = [];
    
    function dfs(v, path = []) {
        visit[v] = true;
        
        for (const next of graph[v - 1]) {
            // if (S.includes(next)) continue; // S の頂点を通るパスはスルー
            if (forbidden.has(next)) continue; // S の頂点を通るパスはスルー
            if (!visit[next]) {
                path.push(next);
                
                if (next === t) {
                    arr.push([...path]); // ←コピー保存重要
                } else {
                    dfs(next, path);
                }
                
                path.pop();
            }
        }
        
        visit[v] = false; 
    }
    
    // スタートを含める
    dfs(s, [s]);
    
    let ans;
    let min = Infinity;
    
    for (const a of arr) {
        if (a.length < min) {
            min = a.length;
            ans = a.join(' ');
        }
    }
    
    console.log(ans ? ans : '-1');
});

🔍 コードの流れ

① 入力取得

• 1行目から n, s, t を取得
• 2行目から k を取得
• 3行目から通ってはいけない頂点集合 S を取得
• S を Set に変換（高速判定用）

② 隣接リスト作成

• 4行目以降を順番に読む
• 各頂点について
  • 隣接頂点数 v を読む（使わない）
  • 隣接頂点の配列を graph に追加
• graph[i] は「頂点 i+1 の隣接頂点」

③ 探索準備

• visit 配列を用意（訪問管理）
• arr 配列を用意（条件を満たすパス保存用）

④ DFS開始

• dfs(s, [s]) を呼び出す
• s から探索スタート
• path に s を入れた状態で開始

🔁 dfs の流れ

1. 今いる頂点 v を訪問済みにする
2. v の隣接頂点を1つずつ確認
3. 次の頂点 next が
   • S に含まれていたらスキップ
   • すでに訪問済みならスキップ
4. 条件を満たすなら path に追加
5. next が t の場合
   • パスをコピーして arr に保存
6. next が t でない場合
   • さらに dfs で探索
7. 探索が終わったら
   • path を元に戻す（pop）
   • 訪問状態も元に戻す

⑤ DFS終了後

• arr に「S を通らない s→t パス」がすべて入る

⑥ 最短パス選択

• arr の中から頂点数が最小のものを選ぶ

⑦ 出力

• 見つかればそのパスを出力
• 見つからなければ -1

📝まとめ

DFSで s→t の全単純パスを探索し、S を含まないものだけ保存し、その中から最短を出力する