백준 14395번 4연산 JavaScript 풀이 [BFS]

백준 14395번 4연산 문제를 자바스크립트로 BFS 알고리즘을 이용해서 풀어보았다. 

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

 

1) 메모리 초과로 실패

new Array(t+1)이 문제인 듯 하다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let [s, t] = input[0].split(' ').map(Number);

if (s == t) {
  console.log(0);
  process.exit();
}

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

// [연산수, 연산과정]
let visited = new Array(t+1).fill().map(_ => [0, ""]);
visited[s] = [1, ""]
queue = new Queue();
queue.enqueue(s)

// BFS 진행
while (queue.getLength() != 0) {
  // 현재값
  let x = queue.dequeue();
  // 연산 이후 값
  let next;

  // 연산 반복
  for (let op of ["*", "+", "-", "/"]) {
    if (op == "*") next = x * x;
    else if (op == "+") next = x + x;
    else if (op == "-") next = x - x;
    else if (op == "/") {
      if (x != 0) next = x / x;
      else next = x;
    }
    
    // 범위 벗어나면 무시
    if (next > t) continue;

    // 나왔던 결과값이 아닐 경우
    if (visited[next][0] == 0) {
      queue.enqueue(next)
      visited[next] = [visited[x][0] + 1, visited[x][1] + op];
    }
  }
}

if (visited[t][0] == 0) console.log(-1);
else console.log(visited[t][1])

 

2) Map객체 이용해서 통과!

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let [s, t] = input[0].split(' ').map(Number);

if (s == t) {
  console.log(0);
  process.exit();
}

class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const element = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return element;
  }
  getLength() {
    return this.tail - this.head;
  }
}

// [연산수, 연산과정]
let visitedMap = new Map();
queue = new Queue();
queue.enqueue(s)
visitedMap.set(s, "")

// BFS 진행
while (queue.getLength() != 0) {
  // 현재값
  let x = queue.dequeue();
  
  // 연산 이후 값
  let next;

  // 연산 반복
  for (let op of ["*", "+", "-", "/"]) {
    if (op == "*") next = x * x;
    else if (op == "+") next = x + x;
    else if (op == "-") next = x - x;
    else if (op == "/") {
      if (x != 0) next = x / x;
      else next = x;
    }
    
    // 범위 벗어나면 무시
    if (next > t) continue;

    // 나왔던 결과값이 아닐 경우
    if (!visitedMap.has(next)) {
      queue.enqueue(next)
      visitedMap.set(next, visitedMap.get(x) + op);
    }
  }
}

if (!visitedMap.get(t)) console.log(-1);
else console.log(visitedMap.get(t))