백준 node.js 16920번 확장 게임 JavaScript JS BFS

16920번: 확장 게임

1. 이 문제는 2중 Queue를 구현하는 문제라 생각됩니다.
2. value값으로 Queue를 가지는 배열 Queue를 만들어, 배열 Queue를 순회하면서 내부 Queue를 순회하는 방식으로 문제를 풀었습니다.

문제 풀이

let fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const [N,M,P] = input[0].split(" ").map(Number);
const sArr = [-1,...input[1].split(" ").map(Number)]
const data = input.slice(2).map(v=>v.split(""))

//Queue 구현
class Node{
  constructor(value){
    this.cur = value;
    this.next = null;
  }
}
class Queue{
  constructor(){
    this.front = null;
    this.rear = null;
    this.length = 0;
  }
  add(value){
    const node = new Node(value)
    if(this.length === 0){
      this.front = node;
    }else {
      this.rear.next = node;
    }
    this.rear = node;
    this.length++
  }
  dequeue(){
    const returnValue = this.front.cur
    this.front = this.front.next
    this.length--
    return returnValue
  }
}
// 1. 처음 위치를 찾고, Queue에 넣는다.
// 2. Queue는 2차원, 순서는 Player순서대로..
// 3. Queue가 존재하지 않을 때 까지 순회.
const answer = Array(P).fill(0)

//초기 상태
const queue = Array.from({length:P}, () => new Queue());
for(let i=0; i<N; i++){
  for(let j=0; j<M; j++){
    if(data[i][j] !== "." && data[i][j] !== "#"){
      // {a : y좌표, b : x좌표, player : 플레이어 숫자, count : 전진 가능 횟수}
      queue[+data[i][j]-1].add({a:i, b:j, player : +data[i][j], count : sArr[+data[i][j]]})
      answer[+data[i][j]-1]++
    }
  }
}

const next = [[0,1],[0,-1],[1,0],[-1,0]]
let i = 0;
//배열 Queue 순회
while(queue.length > i){
  const currentQ = queue[i]
  const nextQ = new Queue();
	//내부 Queue 순회
  while (queue.length > i) {
  const currentQ = queue[i];
  const nextQ = new Queue();
  while (currentQ.length > 0) {
    const { a, b, player, count } = currentQ.dequeue();
    for (let [a2, b2] of next) {
      const A = a + a2;
      const B = b + b2;
      if (A >= 0 && A < N && B >= 0 && B < M) {
        if (data[A][B] === ".") {
          data[A][B] = player;
          answer[player - 1]++;
          if (count !== 1)
            currentQ.add({ a: A, b: B, player, count: count - 1 });
					//더 이상 전진할 수 없다면 nextQ에 넣는다
          if (count === 1)
            nextQ.add({ a: A, b: B, player, count: sArr[player] });
        }
      }
    }
  }
	//배열 Queue에 enqueue하기.
  if (nextQ.length > 0) queue.push(nextQ);
  i++;
}
console.log(answer.join(" "));