グラフのウォーク

今回は paiza の「グラフのウォーク」の問題に挑戦！

🧩 問題概要

■ グラフの特徴

• 頂点は 1〜n
• 無向グラフ
• 完全グラフ
  • 任意の2頂点の間に必ず辺がある
  • つまり、自分以外のすべての頂点に移動可能

■ 与えられるもの

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

■ やること

• 頂点 s からスタート
• 「隣接頂点のどれか」に移動
• それを k回繰り返す
• 訪れた頂点を順番に出力する
• 出力個数は k+1個（最初のs含む）

■ ウォークとは？

• 同じ頂点を何回通ってもOK
• 同じ辺を何回通ってもOK
• 「とにかく移動できればよい」
  
  
  

入力例:

3 1 2

出力例:

1 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 = []; // 隣接リスト
    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 walk = [s];
    let cur = s;
    
    for (let i = 0; i < k; i++) {
        const neighbors = graph[cur];
        const next = neighbors[Math.floor(Math.random() * neighbors.length)];
        cur = next;
        walk.push(cur);
    }
    
    console.log(walk.join(' '));
});

🔍コードの流れ

① 完全グラフの隣接リスト作成

• 各頂点 i について
• 自分以外の 1〜n をすべて追加
• graph[i] に格納

例（n=3）：

• 1 → [2,3]
• 2 → [1,3]
• 3 → [1,2]

② ウォーク生成

• walk配列に最初の s を入れる
• 現在地 cur を s にする
• k回ループ
  • 現在地の隣接頂点を取得
  • その中から1つ選ぶ
  • 移動
  • walkに追加

③ 出力

• walk をスペース区切りで出力

※補足解説

const next = neighbors[Math.floor(Math.random() * neighbors.length)];

🧩 分解して説明

① neighbors.length

• 隣接頂点の個数
• 例：[2,3,4] なら 3

② Math.random()

• 0以上1未満のランダムな小数を返す
• 例：0.23 や 0.87 など

③ Math.random() * neighbors.length

• 0 以上 length 未満の小数になる
• 例（length = 3）：
  • 0.23 × 3 = 0.69
  • 0.87 × 3 = 2.61

④ Math.floor(...)

• 小数を切り捨てる
• 0.69 → 0
• 2.61 → 2

つまり

👉 0 〜 (length-1) の整数を作っている

⑤ neighbors[その整数]

• 配列のその位置の要素を取得

例：

• neighbors = [2,3,4]
• 乱数結果が 1
  → neighbors[1] → 3

📝まとめ

ウォークとは頂点と枝の反復を許す経路のこと。