[백준] 14503번: 로봇 청소기 - Node.js (자바스크립트)

1. 문제 ㅡ 14503번: 로봇 청소기 (난이도: Gold V)

14503번: 로봇 청소기

2. 풀이 ㅡ Node.js (자바스크립트)

class Queue {
  constructor(initValue) {
    this.q = initValue ? [initValue] : [];
    this.head = 0;
    this.tail = initValue ? 1 : 0;
  }

  push(item) {
    this.q[this.tail] = item;
    this.tail++;
  }

  shift() {
    this.head++;
    return this.q[this.head - 1];
  }

  isEmpty() {
    return this.head === this.tail;
  }
}

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const getRobotMoves = input => {
  const [Y, X] = input.shift().split(' ').map(val => +val);
  const [sY, sX, direction] = input.shift().split(' ').map(val => +val);
  const room = input.map(row => row.split(' ').map(val => +val));
  
  /**
  * @cleaned: 이미 청소 완료한 칸의 좌표 저장
  * @dirs: 0 - 상, 1 - 우, 2 - 남, 3 - 좌
  */ 
  const cleaned = Array.from({ length: Y }).map(() => Array.from({ length: X }, () => false));
  const dirs = { 0: [0, -1], 1: [1, 0], 2: [0, 1], 3: [-1, 0] };
  
  const q = new Queue([sX, sY, direction]); 
  let moves = 0;

  while (!q.isEmpty()) {
    let [x, y, direction] = q.shift(); 

    if (room[y][x] === 0 && !cleaned[y][x]) {
      moves += 1;
      cleaned[y][x] = true; 
    }

    for (let i = 0; i < 4; i++) {
      direction = direction - 1 < 0 ? (direction - 1) + 4 : direction - 1;
      const [newX, newY] = [x + dirs[direction][0], y + dirs[direction][1]];
      
      if (room[newY][newX] === 0 && !cleaned[newY][newX]) {
        q.push([newX, newY, direction]);
        break; 
      } 

      if (i === 3) {
        const back = direction - 2 < 0 ? (direction - 2) + 4 : direction - 2;
        const [backX, backY] = [x + dirs[back][0], y + dirs[back][1]];
    
        if (room[backY][backX] === 0) q.push([backX, backY, direction]);
      }
    }
  }

  return moves; 
};

console.log(getRobotMoves(input));

 

2-1. 풀이 설명

로봇 청소기의 동작 방식만 이해하면 어렵지 않은 BFS 문제다. ▼

로봇 청소기의 출발 지점(좌표)과 방향을 queue에 넣어두고 BFS를 하면 된다.

 

• 현재 로봇 청소기가 위치한 칸이 청소되지 않은 상태면 현재 칸을 청소한다 (= moves를 1 증가 시킨다)
• 현재 로봇 청소기의 방향(동서남북)을 기준으로 반시계 방향으로 회전한다. 0, 1, 2, 3을 상, 좌, 하, 우로 지정해두었고, 로봇 청소기의 방향에서 1을 빼서 (음수인 경우 1을 뺀 후 4를 더해줌) 회전된 방향을 계산했다.   
• 회전 후 정면에 청소되지 않은 칸이 있는 경우 청소기를 해당 칸으로 이동, 즉 queue에 새로운 좌표와 현재 방향을 넣어줬다
• 인접 칸을 모두 확인했는데 청소할 수 있는 칸이 없는 경우, 청소기가 후진할 수 있는 칸이 있는지 확인한 후 후진시켰다. 후진 방향을 계산하기 위해 청소기의 현재 방향에서 2를 뺐다 (음수인 경우 2를 뺀 후 4를 더해줌). 청소기가 후진할 때는 현재 방향을 유지하므로, queue에 새로운 좌표와 방향을 넣어줄 때 방향은 원래 방향을 다시 넣어줘야 한다.