[BOJ 3190] 뱀

문제

뱀

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

 

 

풀이

설명

게임이 몇 초에 끝나는 지를 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킵니다.
2. 만약 벽이나 자기 자신의 몸과 부딪히면 게임이 끝납니다.
3. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않습니다.
4. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워줍니다. 즉, 몸길이는 변하지 않습니다.

 

뱀의 현재 방향과 몸이 위치한 좌표를 추적해야 합니다.

큐를 이용하면 몸이 위치한 좌표를 쉽게 추적할 수 있습니다. 이때는 머리의 위치를 추가로 추적해줘야 합니다.

 

예시 코드

function solution() {
  const N = Number(input());
  const K = Number(input());
  const [EMPTY, APPLE, BODY] = [0, 1, 2];
  const [EAST, SOUTH, WEST, NORTH] = [0, 1, 2, 3];
  let direction = EAST;
  const board = Array.from({ length: N }, () => Array(N).fill(0));
  const queue = new Queue();

  for (let i = 0; i < K; i++) {
    const [x, y] = input().split(" ").map(Number);
    board[x - 1][y - 1] = APPLE;
  }

  board[0][0] = BODY;
  queue.enqueue([0, 0]);
  let [hx, hy] = [0, 0];

  const L = Number(input());
  let time = 0;

  for (let i = 0; i < L; i++) {
    const [X, C] = input().split(" ");
    for (let j = time; j < X; j++) {
      const canContinue = move();
      time++;
      if (!canContinue) return time;
    }
    if (C === "L") direction = (direction + 3) % 4;
    else direction = (direction + 1) % 4;
  }

  while (true) {
    const canContinue = move();
    time++;
    if (!canContinue) return time;
  }

  function move() {
    if (direction === EAST) hy += 1;
    else if (direction === WEST) hy -= 1;
    else if (direction === SOUTH) hx += 1;
    else hx -= 1;

    if (hx < 0 || hy < 0 || hx >= N || hy >= N) return false;
    if (board[hx][hy] === BODY) return false;

    if (board[hx][hy] === EMPTY) {
      const [tx, ty] = queue.dequeue();
      board[tx][ty] = EMPTY;
    }
    queue.enqueue([hx, hy]);
    board[hx][hy] = BODY;

    return true;
  }
}