Node.js) 백준 12851번: 숨바꼭질 2

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

class Node {
  constructor(item) {
    this.item = item;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(item) {
    const node = new Node(item)
    if (this.head == null) {
      this.head = node;
    } else {
      this.tail.next = node;
    }

    this.tail = node;
    this.length += 1;
  }

  pop() {
    const popItem = this.head;
    this.head = this.head.next;
    this.length -= 1;
    return popItem.item;
  }
}
const fs = require('fs');
const [S, E] = fs.readFileSync("./dev/stdin").toString().trim().split(" ").map(Number);


function solve(start, end) {
  let dist = Array.from(Array(100001), () => 0)
  let cnt = Array.from(Array(100001), () => 0)
  if (start == end) {
    return [0, 1];
  } else {
    let q = new Queue();
    q.push(S);
    cnt[S] = 1;
    while (q.length > 0) { //큐에 뭐가 들어 있으면
      const now = q.pop(); //꺼내서
      const next = [now + 1, now - 1, now * 2].filter(v => v >= 0 && v <= 100000);
      next.forEach(v => {
        if (dist[v] == 0) {
          q.push(v);
          dist[v] = dist[now] + 1;
          cnt[v] += cnt[now];
        } else if (dist[v] == dist[now] + 1) {
          cnt[v] += cnt[now]
        }
      })
    }
    return [dist[end], cnt[end]]
  }
}

const [v, c] = solve(S, E);
console.log(v)
console.log(c)