백준 3190번 뱀 JavaScript 풀이 [BFS]

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

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

 

으아 복잡해

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

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

// n x n 보드, 사과의 수 k
let n = Number(input[0]);
let k = Number(input[1]);
let graph = new Array(n+1).fill().map(_ => new Array(n+1).fill(0));
// 사과 정보
for (let i=2; i<=k+1; i++) {
  let [r, c] = input[i].split(' ').map(Number);
  graph[r][c] = 2;
}

// 방향 전환 횟수 l
let l = Number(input[k+2]);
let turn = new Map();
for (let i=k+3; i<=k+2+l; i++) {
  let [s, dir] = input[i].split(' ')
  turn.set(Number(s), dir)
}

// 처음 머리와 꼬리 세팅
let [headR, headC] = [1, 1];
let [tailR, tailC] = [1, 1];
graph[headR][headC] = 1;

// 방향 세팅
let directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
let dirIndex = 0;
let sec = 0;

queue = new Queue();
queue.enqueue([headR, headC]);

while (true) {
  if (turn.get(sec) == "L") dirIndex = dirIndex == 0 ? 3 : dirIndex-1;
  else if (turn.get(sec) == "D") dirIndex = dirIndex == 3 ? 0 : dirIndex+1;
  let dir = directions[dirIndex];

  // 다음 시작점
  let nextR = headR + dir[0];
  let nextC = headC + dir[1];
  
  // 다음칸이 벽이나 자기 자신의 몸과 부딪힌다면
  if (nextR < 1 || nextR > n || nextC < 1 || nextC > n || graph[nextR][nextC] == 1) break;
  
  // 사과가 있다면
  if (graph[nextR][nextC] == 2) {
    // 사과를 없앤다 & 꼬리 위치 그대로
    graph[nextR][nextC] = 1
    queue.enqueue([nextR, nextC])
  } else {
    // 사과가 없다면 꼬리 없애기
    graph[nextR][nextC] = 1
    queue.enqueue([nextR, nextC])
    let deq = queue.dequeue();
    [tailR, tailC] = deq;
    graph[tailR][tailC] = 0;
  }
  
  sec++;
  headR = nextR;
  headC = nextC;
}
console.log(sec+1)