[백준] 3190 뱀 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const n = +input.shift();
const k = +input.shift();
const arr = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));

for (let i = 0; i < k; i++) {
  const [row, col] = input[i].split(" ").map(Number);
  arr[row - 1][col - 1] = 2;
}

const record = [];
for (let i = 0; i < +input[k]; i++) {
  const [time, dir] = input[k + 1 + i].trim().split(" ");
  record.push([+time, dir]);
}

const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];
let time = (curDir = 0);
let head = [0, 0];
let tail = [0, 0];
let dirChangeTime = record[0][0];
const path = [];

while (1) {
  const nx = head[0] + dx[curDir];
  const ny = head[1] + dy[curDir];
  if (nx < 0 || nx >= n || ny < 0 || ny >= n) break;
  else if (arr[nx][ny] === 1) break;
  else {
    if (arr[nx][ny] === 2) {
      arr[nx][ny] = 1;
      path.push([nx, ny]);
      head[0] = nx;
      head[1] = ny;
    } else if (arr[nx][ny] === 0) {
      head[0] = nx;
      head[1] = ny;
      arr[nx][ny] = 1;
      path.push([nx, ny]);
      arr[tail[0]][tail[1]] = 0;
      let next = path.shift();
      tail[0] = next[0];
      tail[1] = next[1];
    }
  }
  time++;

  if (time === dirChangeTime) {
    if (record[0][1] === "D") {
      curDir = (curDir + 1) % 4;
    } else if (record[0][1] === "L") {
      if (curDir - 1 < 0) curDir = 3;
      else curDir = (curDir - 1) % 4;
    }
    record.shift();
    if (record.length === 0) dirChangeTime = 0;
    else dirChangeTime = record[0][0];
  }
}

console.log(time + 1);

✔️ 알고리즘 : 구현

✔️ 사과가 있는 칸은 2로 현재 뱀이 위치해있는 칸은 1로 비어있는 칸은 0으로 설정

✔️ 뱀의 위치를 추적하기 위해 path 배열과 뱀의 head, tail을 좌표로 저장

✔️ dirChangeTime마다 방향전환할 수 있도록 time과 비교

✔️ 벽을 만나거나 자신을 만나는 경우 break문으로 빠져나옴

✔️ 움직인 칸에 사과가 있는 경우
2였던 칸을 1로 바꾸고 path 배열에 좌표 저장, tail은 변함 없으므로 head 좌표만 갱신

✔️ 움직인 칸에 사과가 없는 경우
1로 바꾸고 head 갱신, tail이 한칸 줄어야 하므로 꼬리가 있던 좌표를 0으로 변경하고 path로부터 tail 좌표 갱신

✔️ 위의 과정을 반복하고 시간증가, dirChangeTime과 비교후 dirChangeTime 갱신

✔️ 난이도 : 백준 기준 골드 4