グラフのパス

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

🧩 問題概要

■ グラフ

• 1〜n の頂点
• 完全無向グラフ
• どの頂点からでも他のすべての頂点に行ける

■ 与えられるもの

• n：頂点数
• s：スタート地点
• k：移動回数

■ やること

• s からスタート
• k 回移動する
  ただし…

■ ウォークとの違い

• 一度訪れた頂点には戻れない

入力例：

3 1 2

出力例：

1 2 3

✅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 = [];
    for (let i = 1; i <= n; i++) {
        const a = [];
        
        for (let j = 1; j <= n; j++) {
            if (i !== j) a.push(j);
        }
        
        graph[i] = a;
    }
    
    const visit = [s]; // 訪問済みリスト
    let cur = s;
    
    for (let i = 0; i < k; i++) {
        const neighbors = graph[cur];
        while (true) {
            const next = neighbors[Math.floor(Math.random() * neighbors.length)];
            if (!visit.includes(next)) {
                cur = next;
                visit.push(cur);
                break;
            }
        }
    }
    
    console.log(visit.join(' '));
});

🔍コードの流れ

• readlineで標準入力を受け取る準備をする
• 入力された各行を配列 lines に保存する
• 1行目から
  • 頂点数 n
  • スタート地点 s
  • 移動回数 k
    を取得する
• 完全グラフの隣接リストを作る
  • 各頂点 i について
  • 自分以外の頂点 1〜n を配列に入れる
  • graph[i] に保存する
• 訪問済みリスト visit を用意し、最初に s を入れる
• 現在地 cur を s にする
• k回ループする
  • 現在地の隣接頂点を取得する
  • その中からランダムに1つ選ぶ
  • まだ訪問していなければ
    • 現在地を更新する
    • 訪問済みリストに追加する
  • 訪問済みなら、未訪問が出るまで選び直す
• 最後に、訪問順をスペース区切りで出力する
  
  
  
  
  
  

📝まとめ

パスとは頂点と枝の反復を許さない経路のこと。