paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript りんご拾い（情報を持ちながらの移動）

りんご拾い（情報を持ちながらの移動） (paizaランク B 相当)

解答例

訪れた場所を変数visit、持っているりんごの数をSとして、移動していった。

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));
}    
//各頂点にあるりんごの数 A
const A = lines.slice(N,N*2).map(Number);
//通れる辺
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;
}

//訪れた場所、頂点 1 からスタート
let visit = 1;
//りんごの数
let S = A[0];
console.log(S);
//移動
for (let i = 1; i < N; i++) {
    for (let j = 1; j <= N; j++) {
        if (g[visit - 1][j - 1] === 1) {
            //後戻りせずに
            g[j - 1][visit - 1] = 0;
            //頂点jに移動
            visit = j;
            //りんごを拾う
            S += A[j - 1];
            console.log(S);
            break;
        }
    }    
}

解答例(Python3の場合参考)

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

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;
}

//りんごの配列
const apples = lines.slice(n).map(Number);

let s = 0;//りんごの数
let index = 0;//頂点1から
for (let i = 1; i <= n; i++) {
  s += apples[index];
  console.log(s);
  if (g[index].includes(1)) {
    let next_index = g[index].indexOf(1);//次の頂点
    g[next_index][index] = 0;//もどらないように0に書き換え
    index = next_index;//次の頂点へ更新
  }
}

解答例(Ruby の場合参考)

前問のコードに、りんごの数をhavingで表し、appleにりんごの配列を収めて、実装しました。

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;
}

//りんごの配列
const apple = lines.slice(n).map(Number);

let having = 0;//りんごの数
let from = 1;//現在の頂点
let visited = Array(n).fill(false);//訪れた頂点を管理
while (true) {
  having += apple[from - 1];
  console.log(having);
  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++の場合参考)

前問のコードに、変数sumでりんごの数を表し、applesでりんごの配列を収めて、実装します。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//グラフの頂点の数 N
const N = Number(lines[0]);

let sum = 0;//りんごの数
//隣接行列graph
const graph = Array(N).fill(0).map(v => v = []);//[]の二次元配列に

let visit = [];//訪問した頂点番号を管理
let done = Array(N).fill(0);//未訪問0、訪問済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);
}

//りんごの配列
const apples = lines.slice(N).map(Number);

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

//探索
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;//訪問済みに
      sum += apples[graph[now][j]];//りんごの数を足す
    }
  }
  console.log(sum);
}