paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 一方通行（グラフ上の移動）

一方通行（グラフ上の移動） (paizaランク B 相当)

解答例

幅優先探索をします。訪れた場所を配列visitedに保存し、今いる場所を変数nowで管理します。後戻りしないので、訪れた頂点は1を0に書き換えます。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//グラフの頂点の数 N
const N = Number(lines[0]);
//隣接行列g
let g = [];
for (let i = 1; i <= N; i++) {
    g.push(Array(N).fill(0));
}    
for (let i = 1; i <= N - 1; i++) {
    //各辺の両端の頂点 a_i , b_i 
    const [a, b] = lines[i].split(" ").map(Number);
    //配列
    g[a - 1][b - 1] = 1;
    g[b - 1][a - 1] = 1;
}

//移動
let visited = [1]; //訪れた場所、１からスタート
let now = 1; //今いる場所
for (let i = 1; i < N; i++) {
    //後戻りせず
    for(let j = 0; j < N; j++) {
        g[j][now - 1] = 0;
    }
    //次へ移動
    now = g[now - 1].indexOf(1) + 1;
    //訪れた場所へpush
    visited.push(now);
}
console.log(visited.join("\n"));

解答例(Python3の場合参考)

現在の頂点を変数indexで管理します。隣接行列を使って、次の頂点を探索します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//グラフの頂点の数 n
const n = Number(lines[0]);
//隣接行列g
const g = Array(n).fill(0).map(v => v = Array(n).fill(0));
for (let i = 1; i <= n - 1; i++) {
    //各辺の両端の頂点 a_i , b_i 
    const [a, b] = lines[i].split(" ").map(Number);
    g[a - 1][b - 1] = 1;
    g[b - 1][a - 1] = 1;
}

let index = 0;//頂点1から
for (let i = 1; i <= n; i++) {
  console.log(index + 1);//現在の頂点番号を出力していく
  if (g[index].includes(1)) {
    let next_index = g[index].indexOf(1);//次の頂点
    g[next_index][index] = 0;//もどらないように0に書き換え
    index = next_index;//次の頂点へ更新
  }
}

解答例(Ruby の場合参考)

戻らないように配列visitedで管理します。
Rubyの模範解答において、each内ではnextで飛ばせますが、Javascriptにおいては、forEach内ではcontinueで飛ばせないので、ifの条件を工夫しました。"条件を満たしたら飛ばす、満たさなかったら実行する"から、飛ばすのをやめて"条件を満たさなかったら実行する"に変更しました。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//グラフの頂点の数 n
const n = Number(lines[0]);
//隣接行列g
const g = Array(n).fill(0).map(v => v = Array(n).fill(0));
for (let i = 1; i <= n - 1; i++) {
    //各辺の両端の頂点 a_i , b_i 
    const [a, b] = lines[i].split(" ").map(Number);
    g[a - 1][b - 1] = 1;
    g[b - 1][a - 1] = 1;
}

let from = 1;//現在の頂点
let visited = Array(n).fill(false);//訪れた頂点を管理
while (true) {
  console.log(from);
  visited[from - 1] = true;//訪れた頂点をtureに
  let to = 0;//次の頂点
  g[from - 1].forEach((val, i) => {
    //条件を満たしたら実行
    if (!(val === 0 || visited[i])) { //val=0繋がっていない、visited[i]=true訪問済み
      to = i + 1;//繋がっているかつ未訪問なら、次の頂点
    }
  });
  if (to === 0) { //行き先がなくなったら、ループ抜けて終わり
    break;
  }
  from = to;//次の頂点
}

解答例(C++の場合参考)

配列visitで頂点番号を管理、配列doneで訪問済みか管理します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//グラフの頂点の数 N
const N = Number(lines[0]);
//隣接行列graph
const graph = Array(N).fill(0).map(v => v = []);//[]の二次元配列に

let visit = [];//訪問した頂点番号を管理
let done = Array(N).fill(0);//未訪問0、訪問済1で管理

visit.push(0);//はじめに頂点1を訪れる
done[0] = 1;//頂点1を訪問済みに

for (let i = 1; i <= N - 1; i++) {
    //各辺の両端の頂点 a_i , b_i 
    let [a, b] = lines[i].split(" ").map(Number);
    a--;
    b--;
    graph[a].push(b);
    graph[b].push(a);
}
//探索
while (visit.length !== N) {
  let now = visit[visit.length - 1];//現在地
  for (let j = 0; j < graph[now].length; j++) {
    if (done[graph[now][j]] === 0) { //未訪問なら
      visit.push(graph[now][j]);//訪問した頂点を追加
      done[graph[now][j]] = 1;//訪問済みに
    }
  }
}
//出力
for (let i = 0; i < N; i++) {
  console.log(visit[i] + 1);
}