백준 / 3190번 / 뱀 / JS

풀이

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

let N, K, L;
const snakeDirInfo = [];
let snakeDirInfoIndex = 0;

const APPLE = 1;
const EMPTY = 0;
const SNAKE = -1;
let board;

// 상, 우, 하, 좌
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

function init() {
  N = +input.shift();
  K = +input.shift();

  board = Array.from({ length: N }, () =>
    Array.from({ length: N }, () => EMPTY)
  );

  for (let i = 0; i < K; i++) {
    const [row, col] = input.shift().split(' ').map(Number);
    board[row - 1][col - 1] = APPLE;
  }

  L = +input.shift();

  for (let i = 0; i < L; i++) {
    const [X, C] = input.shift().split(' ');
    snakeDirInfo.push([+X, C]);
  }
}

function isValid(row, col) {
  return 0 <= row && row < N && 0 <= col && col < N;
}

function play() {
  const queue = [[0, 0]];
  let curDir = 1; // 뱀은 처음에 오른쪽을 향한다.
  let seconds = 0;

  board[0][0] = SNAKE;

  while (true) {
    seconds++;

    const [headRow, headCol] = queue.at(-1);
    const [tailRow, tailCol] = queue[0];
    const [nr, nc] = [headRow + dr[curDir], headCol + dc[curDir]];

    // 벽에 부딪히면 게임을 종료한다.
    if (!isValid(nr, nc)) {
      return seconds;
    }

    // 뱀이 자기 몸에 부딪히면 게임을 종료한다.
    if (board[nr][nc] === SNAKE) {
      return seconds;
    } else if (board[nr][nc] === APPLE) {
      // 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
      board[nr][nc] = SNAKE;
    } else {
      // 만약 이동한 칸에 사과가 없다면, 몸 길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸 길이는 변하지 않는다.
      board[nr][nc] = SNAKE;
      board[tailRow][tailCol] = EMPTY;
      queue.shift();
    }

    queue.push([nr, nc]);

    // 방향 전환 정보가 있으면 방향 전환한다.
    if (snakeDirInfoIndex < snakeDirInfo.length) {
      const [X, C] = snakeDirInfo[snakeDirInfoIndex];

      // 방향 전환 시간이 되면 방향 전환한다.
      if (X === seconds) {
        if (C === 'L') {
          // 왼쪽으로 방향 전환한다.
          curDir = curDir - 1 < 0 ? 3 : curDir - 1;
        } else if (C === 'D') {
          // 오른쪽으로 방향 전환한다.
          curDir = (curDir + 1) % 4;
        }
        // 다음 방향 전환 정보 인덱스를 증가시킨다.
        snakeDirInfoIndex++;
      }
    }
  }
}

function solution() {
  init();
  const seconds = play();

  console.log(seconds);
}

solution();

일반적인 구현 문제이다.

구현하다보니 코드가 길어져서 함수를 분리해서 작성했다.

 

변수들

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

let N, K, L;
const snakeDirInfo = [];
let snakeDirInfoIndex = 0;

const APPLE = 1;
const EMPTY = 0;
const SNAKE = -1;
let board;

// 상, 우, 하, 좌
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

• N: 보드의 크기
• K: 사과의 개수
• L: 뱀의 방향 변환 횟수
• snakeDirInfo: 뱀의 방향 전환 정보를 담는 배열
• snakeDirInfoIndex: snakeDirInfo 배열에서 현재 어느 방향 전환 정보를 참조하고 있는지 확인하는 인덱스
• APPLE, EMPTY, SNAKE: 각각 board에 사과, 빈 공간, 뱀인지 상태를 나타낼 변수
• board: 보드의 상태를 나타내는 2차원 배열
• dr, dc: 사방으로 이동하는 정보

 

`init()`

function init() {
  N = +input.shift();
  K = +input.shift();

  board = Array.from({ length: N }, () =>
    Array.from({ length: N }, () => EMPTY)
  );

  for (let i = 0; i < K; i++) {
    const [row, col] = input.shift().split(' ').map(Number);
    board[row - 1][col - 1] = APPLE;
  }

  L = +input.shift();

  for (let i = 0; i < L; i++) {
    const [X, C] = input.shift().split(' ');
    snakeDirInfo.push([+X, C]);
  }
}

각 필요한 정보들을 문제의 입력에 맞게 초기화하는 함수이다.

`board`는 일단 빈 칸으로 모두 초기화해준 뒤, 주어진 사과 위치에 맞춰서 값을 초기화해준다.

문제는 좌상단이 1행 1열로 주어지지만, 배열은 0행 0열로 시작하므로 1씩 빼주어야 하는것에 주의하자.

그 다음으로는 X는 숫자지만, 입력받을 때 문자열로 되기 때문에 숫자로 바꿔서 저장해주자.

 

`isValid()`

function isValid(row, col) {
  return 0 <= row && row < N && 0 <= col && col < N;
}

배열을 다루게 된다면 꼭 구현하게 되는 범위 체크 함수이다.

많이 사용하는 함수니, 본인 스타일대로 구현하면 된다.

 

사실 예전엔 명확히 하기 위해 다음과 같이 구현했었다.

function isValid(row, col) {
  if (row < 0 || row >= N) {
    return false;
  }
  if (col < 0 || col >= N) {
    return false;
  }

  return true;
}

나중엔 빠르게 짜고 싶어서 한줄로 구현했지만,

만약 알고리즘에 익숙하지 않는 초보자라면 명확히 나타내주는게 좋은 것 같다.

알고리즘이라 그렇지, 만약에 프로젝트에서 유틸함수를 구현한다고 하면 위와 같이 구현할 것 같다.

 

`play()`

function play() {
  const queue = [[0, 0]];
  let curDir = 1; // 뱀은 처음에 오른쪽을 향한다.
  let seconds = 0;

  board[0][0] = SNAKE;

  while (true) {
    seconds++;

    const [headRow, headCol] = queue.at(-1);
    const [tailRow, tailCol] = queue[0];
    const [nr, nc] = [headRow + dr[curDir], headCol + dc[curDir]];

    // 벽에 부딪히면 게임을 종료한다.
    if (!isValid(nr, nc)) {
      return seconds;
    }

    // 뱀이 자기 몸에 부딪히면 게임을 종료한다.
    if (board[nr][nc] === SNAKE) {
      return seconds;
    } else if (board[nr][nc] === APPLE) {
      // 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
      board[nr][nc] = SNAKE;
    } else {
      // 만약 이동한 칸에 사과가 없다면, 몸 길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸 길이는 변하지 않는다.
      board[nr][nc] = SNAKE;
      board[tailRow][tailCol] = EMPTY;
      queue.shift();
    }

    queue.push([nr, nc]);

    // 방향 전환 정보가 있으면 방향 전환한다.
    if (snakeDirInfoIndex < snakeDirInfo.length) {
      const [X, C] = snakeDirInfo[snakeDirInfoIndex];

      // 방향 전환 시간이 되면 방향 전환한다.
      if (X === seconds) {
        if (C === 'L') {
          // 왼쪽으로 방향 전환한다.
          curDir = curDir - 1 < 0 ? 3 : curDir - 1;
        } else if (C === 'D') {
          // 오른쪽으로 방향 전환한다.
          curDir = (curDir + 1) % 4;
        }
        // 다음 방향 전환 정보 인덱스를 증가시킨다.
        snakeDirInfoIndex++;
      }
    }
  }
}

메인 로직인 함수이다.

핵심 아이디어는, queue에 뱀이 있는 좌표를 모두 넣어주는 것이다.

처음에 뱀은 0행 0열에서 시작하므로 queue에 [0, 0]을 넣어주고 시작한다.

그 뒤로는 문제대로 쭉 구현해주면 된다.

 

주의할 것은 방향전환 할 때이다.

문제에서 방향 전환은 X초가 끝난 후에 한다고 나와있기 때문에 마지막에 해주어야 한다.

 

그리고 어이없이 헤맸던게 있는데...

왼쪽 방향전환이 'L'이라서 Left의 첫번째 알파벳이고,

오른쪽이 당연히 'R'인줄 알고 'R'로 문제를 풀다가 계속 답이 틀렸다...

오른쪽은 'R'이 아니라 'D'입니다!!!

 

`solution()`

function solution() {
  init();
  const seconds = play();

  console.log(seconds);
}

함수를 분리해놔서 메인 함수는 깔끔하게 구성할 수 있었다.