[백준 3190 - Node.js] 뱀

🔗 문제 링크

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

3190번: 뱀

✏️ 풀이

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const [N, K] = input.slice(0, 2).map(Number);
const apples = input.slice(2, 2 + K).map(v => v.split(' ').map(Number));
const rotations = input
  .slice(K + 3)
  .reduce((acc, v) => {
    const [time, direction] = v.split(' ');
    acc[time] = direction === 'L' ? -1 : 1;
    return acc;
  }, {});
const board = [...Array(N)].map(() => Array(N).fill(0));
apples.forEach(([x, y]) => board[x - 1][y - 1] = 2);
const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];

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

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

  enqueue(value) {
    const node = new Node(value);
    if (!this.size) {
      this.head = node;
      this.tail = node;
    } else {
      this.head.next = node;
      this.head = node;
    }
    this.size++;
  }

  dequeue() {
    if (!this.size) {
      return;
    }
      
    const deletedNodeValue = this.tail.value;
      
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.next;
    }
    this.size--;
    return deletedNodeValue;
  }
}

const snake = new Queue();
snake.enqueue([0, 0]);
let direction = 0;
let time = 0;

while (true) {
  time++;
  const [x, y] = snake.head.value;
  const [dx, dy] = offset[direction];
  const nx = x + dx;
  const ny = y + dy;

  if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] === 1) {
    break;
  }

  if (!board[nx][ny]) {
    const [tx, ty] = snake.dequeue();
    board[tx][ty] = 0;
  }

  snake.enqueue([nx, ny]);
  board[nx][ny] = 1;

  direction = (direction + 4 + (rotations[time] ?? 0)) % 4;
}

console.log(time);

board에 빈 칸은 0, 뱀이 있는 칸은 1, 사과가 있는 칸은 2로 표시하였다.

직접 큐를 구현하여 매 초마다 뱀을 이동시키면서 enqueue하고, 빈 칸으로 이동했을 때에는 뱀의 꼬리 칸을 dequeue하였다. 그리고 뱀의 머리가 이동할 칸이 board 범위 밖이거나 자기 자신의 몸일 경우에는 반복을 종료하도록 하였다.

 

 

✏️ 다른 풀이

const input = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');
const [N, K] = input.slice(0, 2).map(Number);
const apples = input.slice(2, 2 + K).map(v => v.split(' ').map(Number));
const rotations = input
  .slice(K + 3)
  .reduce((acc, v) => {
    const [time, direction] = v.split(' ');
    acc[time] = direction === 'L' ? -1 : 1;
    return acc;
  }, {});
const board = [...Array(N)].map(() => Array(N).fill(0));
apples.forEach(([x, y]) => board[x - 1][y - 1] = 2);
const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];

const snake = [[0, 0]];
board[0][0] = 1;
let direction = 0;
let tailIndex = 0;
let time = 0;

while (true) {
  time++;
  const [x, y] = snake[snake.length - 1];
  const [dx, dy] = offset[direction];
  const nx = x + dx;
  const ny = y + dy;

  if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] === 1) {
    break;
  }

  if (!board[nx][ny]) {
    const [tx, ty] = snake[tailIndex];
    board[tx][ty] = 0;
    tailIndex++;
  }

  snake.push([nx, ny]);
  board[nx][ny] = 1;

  direction = (direction + 4 + (rotations[time] ?? 0)) % 4;
}

console.log(time);

큐를 구현하지 않고 인덱스를 활용하여 해결할 수도 있다.

일반 배열에 뱀이 이동할 때마다 계속해서 좌표를 push하고, 빈 칸으로 이동할 때 뱀의 꼬리 칸을 shift하지 않고 그냥 두고 꼬리칸을 가리키는 index만 증가시키는 방식이다.