グラフのトレイル 2

今回は paiza の「グラフのトレイル 2」の問題に挑戦！

🧩 問題概要

🔽 与えられるもの
・頂点数 n の無向グラフ（1〜n）
・始点 s
・移動回数 k
・各頂点の隣接リスト

🔽 グラフの特徴
・無向グラフ
・自己ループなし
・多重辺なし

🔽 やること
・頂点 s からスタート
・ちょうど k 回移動する経路をすべて求める

🔽 トレイルの定義（超重要）
・同じ辺は2回使えない（←最重要）
・頂点は何回通ってもOK

🔽 出力
・1行目：トレイルの総数
・2行目以降：各経路（頂点の列）
　→ 長さは k+1 個（始点含む）

入力例:

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

出力例:

2
2 3 4 2 1
2 4 3 2 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, k] = lines[0].split(' ').map(Number);
   
   const graph = [['dummy']];
   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.from({ length: n+1}, () => []); // 訪問済みリスト(隣接リスト)
   const trails = [];
   
   function dfs(v, trail, edges, k) { // v = 現在地（現在の頂点）、trail = トレイルで訪れる頂点を順に並べた配列、edges = 通過済みの枝の配列、k = 残りの移動回数
       if (k === 0) {
           trails.push([...trail]); // コピーして保存
       } else {
           for (const next of graph[v]) {
               if (!edges[v][next]) {
                   edges[v][next] = true;
                   edges[next][v] = true;
                   
                   trail.push(next);
                   
                   dfs(next, trail, edges, k-1);
                   
                   edges[v][next] = false;
                   edges[next][v] = false;
                   
                   trail.pop();
               }
           }
       }
   }
   
   dfs(s, [s], visit, k);
   console.log(trails.length);
   trails.forEach(t => console.log(t.join(' ')));
});

🔍コードの流れ

🔽 全体の流れ
・入力を読み取る（n, s, k とグラフ構造）
・隣接リスト graph を作る
・「使った辺」を記録する配列 visit を用意
・結果を入れる trails を用意
・DFSをスタート（始点 s から）

🔽 DFSの流れ
・今いる頂点 v からスタート
・残り移動回数 k を見ながら探索

🔽 終了条件
・k が 0 になったら
　→ 今までの経路（trail）をコピーして保存

🔽 探索処理
・今の頂点 v に隣接する頂点 next を1つずつ見る
・まだ使っていない辺（v → next）だけ使う

🔽 次の頂点へ進むとき
・その辺を「使用済み」にする（両方向）
・trail に next を追加
・次の頂点へ再帰（k を1減らす）

🔽 戻るとき（バックトラッキング）
・使った辺を「未使用」に戻す
・trail から最後の頂点を削除

🔽 最後
・すべての経路を探索し終えたら
・経路の数を出力
・各経路を1行ずつ出力

📝まとめ

🔽DFSの典型パターン
・「全列挙」→ DFSで探索
・条件を満たす経路だけ記録

🔽一番重要な考え方
・今回は「頂点」じゃなくて
👉 「辺」を使ったか管理する

🔽状態管理
・edges[a][b] で辺の使用状況を管理
・無向グラフなので
　→ a→b と b→a を両方管理

🔽バックトラッキング
・進むとき → 使用済みにする
・戻るとき → 未使用に戻す

👉 これで「全パターン探索」ができる

🔽配列の扱い（超重要）
・そのまま保存 → 参照でバグる
・コピーして保存 → 正しい結果

🔽この問題のまとめ
👉「辺の再利用を禁止したDFS全列挙」