Node.js) 백준 13913번: 숨바꼭질 4

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

13913번: 숨바꼭질 4

 

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), () => null)
  let parent = Array.from(Array(100001), () => 0)
  if (start == end) {
    console.log(0);
    console.log(start);
    return;
  } else {
    let q = new Queue();
    q.push(S);
    dist[S] = 0;
    parent[S] = null;
    while (q.length > 0) { //큐에 뭐가 들어 있으면
      const now = q.pop(); //꺼내서
      if (now == end) {
        let ele = now;
        const answer = [];
        while (ele != null) {
          answer.unshift(ele);
          ele = parent[ele];
        }
        console.log(dist[now])
        console.log(answer.join(' '))
        return;
      }
      const next = [now + 1, now - 1, now * 2]
      next.forEach(v => {
        if (v >= 0 && v <= 100000 && dist[v] == null) {
          q.push(v);
          dist[v] = dist[now] + 1;
          parent[v] = now;
        }
      })
    }
  }
}
solve(S, E);