トレイルの経由地

今回は paiza の「トレイルの経由地」の問題に挑戦！

問題概要

・頂点 1 ～ n の 無向グラフ が与えられる
・グラフは 隣接リスト形式 で入力される

・次の 3 つの頂点が指定される
　- s：スタート
　- t：ゴール
　- p：できるだけ多く通りたい頂点

・トレイル を考える
　- 辺は同じものを2回使えない
　- 頂点は何回通ってもよい

・条件
　- s から t まで進むトレイル
　- 頂点 p を通る回数が最大

・その条件を満たすトレイルを 1つ出力する

・もし
　s → t のトレイルで p を通るものが存在しない場合
　→ -1 を出力

・出力形式
　- 通った頂点を 順番にスペース区切りで出力
　- 先頭は s
　- 最後は t

※ s や t は途中で再び通る可能性がある

入力例:

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

出力例:

1 5 2 3 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, p] = lines[0].split(' ').map(Number);
    
    const graph = [];
    
    for (let i = 2; i <= n * 2; i++) {
        if (i % 2 === 0) {
            graph.push(lines[i].split(' ').map(Number));
        }
    }
    
    const visit = Array.from({ length: n+1 }, () => Array(n+1).fill(false));
    const trails = [];
    
    function dfs(v, trail, edges) {
        for (const next of graph[v - 1]) {
            if (!edges[v][next]) {
                edges[v][next] = true;
                edges[next][v] = true;
                
                trail.push(next);
                
                if (next === t) {
                    if (trail.includes(p)) trails.push([...trail]);
                    dfs(next, trail, edges); // t を通過して探索
                } else {
                    dfs(next, trail, edges);
                }
                
                edges[v][next] = false;
                edges[next][v] = false;
                
                trail.pop();
            }
        }
    }
    
    dfs(s, [s], visit);
    
    let ans;
    let max = -Infinity;
    
    for (const a of trails) {
        if (a.length > max) {
            max = a.length;
            ans = a.join(' ');
        }
    }
    
    console.log(ans || '-1'); // 頂点 p を通過するトレイルが存在しない場合は -1 を出力
});

🔍コードの流れ

・入力を readline で受け取り、すべての行を lines 配列に保存する

・1行目から
　頂点数 n、開始頂点 s、終了頂点 t、通過したい頂点 p を取得する

・隣接リストを作る
　入力の偶数行から、各頂点につながっている頂点を graph に保存する

・visit 配列を作る
　頂点同士の辺をすでに使ったかどうかを記録するための配列

・条件を満たすトレイルを保存するための trails 配列を用意する

・dfs 関数を作る
　引数は
　現在の頂点 v
　これまで通った頂点の並び trail
　使用済みの辺 edges

・現在の頂点 v から行ける隣接頂点を順番に調べる

・その辺をまだ使っていなければ
　辺を使用済みにして
　trail に次の頂点 next を追加する

・もし next が終点 t なら
　trail の中に p が含まれているか確認する
　含まれていれば、そのトレイルを trails に保存する
　その後も探索は続ける

・next を現在位置として、さらに探索を続ける

・探索から戻るとき
　使った辺を未使用に戻す
　trail の最後の頂点を削除する

・最初の探索として dfs(s, [s], visit) を実行する

・見つかったトレイルの中から、長さが最大のものを探す

・最大のトレイルを出力する
　もし条件を満たすトレイルがなければ -1 を出力する

📝まとめ

前問のコードに p を経由しているかの条件を追加する