[JS][백준]3190_뱀

문제 번호

3190번: 뱀

 

 

 

알고리즘 분류

구현, 자료구조, 시뮬레이션, 덱, 큐

 

문제 풀이

 구현문제다. 그래서 알고리즘은 어렵지 않다. 다 풀고나서 백준에 있는 알고리즘 분류를 보니 덱과 큐 가 있었다. 아마도 뱀의 이동경로를 기록하기 위해서 사용하는 용도같다. 나는 문제풀때는 이 생각을 못해서 배열에 이동경로를 넣고 shift 하면서 뱀의 꼬리를 움직였다.(선입 선출 구조이므로 queue를 생각하고 풀었으면 생각의 정리가 더 편했을것 같다.)

 

JS 스텍, 큐

큐, 스택, 트리 | JavaScript로 만나는 세상

JS 덱

 

자바스크립트로 알고리즘 정리하기 #3 Deque 구현 및 문제풀이

 

 JS에는 shift(), unshift(), push(), pop() 이 구현되어 있으므로 해당 자료구조들을 따로 구현해서 사용하진 않았다. 

하지만 개념들은 알고있어서 한다 생각하여 공부했고 나중에 문제가 복잡해지면 자료구조를 구현하여 손쉽게 가져다 쓰는것이 더 좋아보이기도 한다.

 

 문제에서 요구하는 순서대로 구현하면 된다. JS로 입력을 받을때는 개행문자를 제거하기위해 trim()을 써줘야 한다는걸 다시 알게되었다.

 

뱀이 보고있는 방향, 머리의 위치 그리고 꼬리의 위치를 기록하기위하여 snake 라는 객체를 생성했다.

let snake = {
  'diraction' : 1,
  'head' : [1,1],
  'tail' : [1,1]
};

 

문제에서 주어지는 명령어들을 기록하기위해서 commands 라는 배열을 생성하여 그안에 객체를 집어넣었다.

let commands = [];
const L = input.shift();
for (let i = 0; i < L; i++) {
  let temp = input.shift().trim().split(' ');
  commands[i] = { 
    time: Number(temp[0]),
    diraction: temp[1]
  };      
}

 

 그리고 뱀의 머리가 지나간 자리대로 꼬리도 따라와야 하기때문에 route 라는 배열에 뱀의 이동경로를 기록하기로 했다. 이때 queue와 deque 의 개념이 필요했던것 같다. 

 

 이런 구현 문제들은 문제를 차분하게 읽고 놓치는 조건이 없도록 천천히 푸는게 오히려 빨리푸는 방법이라는걸 다시 느꼇다. 그리고 방향전환을 위해서 diraction 배열을 사용했는데 구현문제에서 방향전환을 하는 경우가 종종있다. 이럴때 인덱스를 증가시키거나 감소시키고 배열의 길이로 % 연산을 하여서 새로운 인덱스를 구하는 방법을 사용했다. 단 이번 문제는 증가만 하는것이 아니고 감소하는 방향도 있기때문에 인덱스가 감소하여 음수가 되면 배열의 최고 인덱스를 갖도록 하는 부분만 추가하였다.

 if(commands[0].diraction === 'D'){
      //console.log('turn Right')
      snake.diraction = (snake.diraction + 1) % 4;
    }
    else if(commands[0].diraction === 'L'){
      //console.log('turn Left')      
      if(snake.diraction - 1 < 0)
        snake.diraction = 3;
      else
        snake.diraction = (snake.diraction - 1) % 4;
    }

 

전체코드

const { ALPN_ENABLED } = require('constants');
const fs = require('fs');
const input = fs.readFileSync('뱀/input.txt').toString().trim().split('\n');
const N = Number(input.shift());
const K = Number(input.shift());
let route = [];
// 북 동 남 서 
const diraction = [ [-1,0], [0,1], [1,0], [0,-1] ];

let apples = [];
for (let i = 0; i < K; i++) {
  apples.push(input.shift().split(' '));
}
apples = apples.map(x => x.map(y => Number(y)));

let commands = [];
const L = input.shift();
for (let i = 0; i < L; i++) {
  let temp = input.shift().trim().split(' ');
  commands[i] = { 
    time: Number(temp[0]),
    diraction: temp[1]
  };      
}

let board = new Array(N+2);
for(let i=0; i<N+2; i++){
  board[i] = new Array(N+2).fill(0);
}
board[1][1] = 's';

for(let i=0; i<N+2; i++){
  board[i][0] = 1;
  board[i][N+1] = 1;
  board[0][i] = 1;
  board[N+1][i] = 1;
}

for(let i=0; i<apples.length; i++){
  board[apples[i][0]][apples[i][1]] = 'a';
}

let snake = {
  'diraction' : 1,
  'head' : [1,1],
  'tail' : [1,1]
};

let gameTime = 0;
let nextCommand = commands[0].time;
while(1){
  let nextY = snake.head[0] + diraction[snake.diraction][0];
  let nextX = snake.head[1] + diraction[snake.diraction][1];
  
  // 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
  if(board[nextY][nextX] === 1 || board[nextY][nextX] === 's'){
    //console.log('gameEnd');    
    // console.log(board);
    //console.log(nextY, nextX);
    //console.log(board[nextY][nextX]);
    //console.log(snake.diraction);
    break;
  }
  else{
    // 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
    if(board[nextY][nextX] === 'a'){
      //console.log('apple!');
      // 사과가 없어진다.
      board[nextY][nextX] = 's';
     
      // 뱀의 이동경로를 기록한다.
      route.push([nextY,nextX]);

      // 뱀의 머리가 이동한다.      
      snake.head[0] = nextY;
      snake.head[1] = nextX;        
    }
    // 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
    else if(board[nextY][nextX] === 0){
      //console.log(nextY, nextX);
      // 뱀의 머리를 이동시킨다.
      snake.head[0] = nextY;
      snake.head[1] = nextX;
      board[snake.head[0]][snake.head[1]] = 's';

      // 뱀의 이동경로를 기록한다.
      route.push([nextY,nextX]);

      // 뱀의 꼬리가 있던 자리를 비운다.
      board[snake.tail[0]][snake.tail[1]] = 0;

      // 뱀의 꼬리를 이동시킨다.
      let nextXY = route.shift();
      snake.tail[0] = nextXY[0];
      snake.tail[1] = nextXY[1];      
    }
  }
  gameTime++;
  // 1초가 지났다.

  // 방향 전환 정보에 따라서 움직인다.  
  if(gameTime === nextCommand){           
    if(commands[0].diraction === 'D'){
      //console.log('turn Right')
      snake.diraction = (snake.diraction + 1) % 4;
    }
    else if(commands[0].diraction === 'L'){
      //console.log('turn Left')      
      if(snake.diraction - 1 < 0)
        snake.diraction = 3;
      else
        snake.diraction = (snake.diraction - 1) % 4;
    }    
    commands.shift();    
    if(commands.length === 0)
      nextCommand = 0;
    else
      nextCommand = commands[0].time;
  }
}
console.log(gameTime+1);

특이사항

 구현문제는 놓친 조건을 여러번 수정하다보면 제대로 썻던 부분도 오타를 내거나 꼬이게 만드는 경우가 많았다. 천천히 풀더라도 한번에 통과시키는게 제일 맘편하다.

 

오타확인을......잘......하자...................ide가 아니였으면 평생 못풀었을지도 모른다....