[JS][백준]14503_로봇 청소기

문제 번호

14503번: 로봇 청소기

 

 

 

알고리즘 분류

• 구현
• 시뮬레이션

 

문제 풀이

 BFS를 활용한 구현 문제이다. 별다른 어려운 내용 없이 흔히 사용하는 BFS를 문제에서 주어진 조건에 맞게 돌리면 된다.

단, 문제에서 '북:0 동:1 남:2 서:3'라고 주어진다. 처음에 이 부분을 놓쳐서 청소기의 회전 방향을 반대로 하는 바람에 시간이 오래 걸렸었다. 

 

 dx, dy 란 배열을 만들어서 동서남북 각 방향으로 회전할 때 좌표의 변화를 나타낼 수 있도록 한다. 이때 문제의 입력과 배열들의 인덱스를 동일하게 해 주기 위해서 입력받은 d를 다음과 같이 수정해주었다.

//북:0 동:1 남:2 서:3
  //북 서 남 동 으로 돌려야함.
  let dx = [0, -1, 0, 1];
  let dy = [-1, 0, 1, 0];

if (d === 0) d = 0
  else if (d === 1) d = 3;
  else if (d === 2) d = 2
  else if (d === 3) d = 1;

  이러면 문제에서 주어진 '북:0 동:1 남:2 서:3' 조건과 dx, dy의 인덱스를 동일하게 사용할 수 있다.

이제 BFS를 활용해서 문제에서 요구하는대로 탐색을 진행하면 된다.

 

 문제에서 4번 회전하면 뒤를 확인하라고 하였으니 그렇게 해준다. 왼쪽으로 90도 회전을 2번 진행하면 뒷 방향이 된다. 그러므로 dx[ (현재방향을 나타내는 인덱스 + 2)  % 4]를 이용했다. (dy도 동일)

if (cnt >= 4) { // 2-b 실행.
        // 뒷 방향 좌표.
        nextX = cx + dx[(cd + 2) % 4];
        nextY = cy + dy[(cd + 2) % 4];
        if (map[nextY][nextX] === 1) { // 정지.
          map2[nextY][nextX] = 9;
          return answer;
        } else {
          q.push(nextX, nextY, cd); // 뒤로 한 칸 후진한다.
          break;
        }
      }

 

전체 코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);

class Node {
  constructor(x, y, d) {
    this.next = null;
    this.x = x;
    this.y = y;
    this.d = d;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  length() {
    return this.size;
  }
  push(x, y, d) {
    let node = new Node(x, y, d);
    if (this.size === 0) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }
  pop() {
    let temp = this.head;
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }
    this.size--;
    return temp;
  }
}
function sol(r, c, d, map, v, map2) {
  let answer = 0;

  //북:0 동:1 남:2 서:3
  //북 서 남 동 으로 돌려야함.
  let dx = [0, -1, 0, 1];
  let dy = [-1, 0, 1, 0];
  
  if (d === 0) d = 0
  else if (d === 1) d = 3;
  else if (d === 2) d = 2
  else if (d === 3) d = 1;

  let q = new Queue();
  q.push(c, r, d);
  v[r][c] = true;
  map2[r][c] = 4
  answer++;

  while (q.length()) {
    let cur = q.pop();
    let [cx, cy, cd] = [cur.x, cur.y, cur.d];

    let cnt = 1;
    while (1) {
      // 왼쪽으로 회전한다.
      let nextX = cx + dx[(cd + cnt) % 4];
      let nextY = cy + dy[(cd + cnt) % 4];

      // 다음 진행 경로가 범위 안에 있을때.
      if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N && map[nextY][nextX] === 0 && !v[nextY][nextX]) {
        q.push(nextX, nextY, (cd + cnt) % 4); // 다음 진행방향.
        v[nextY][nextX] = true;
        map2[nextY][nextX] = 4
        answer++;
        break;
      }
      if (cnt >= 4) { // 2-b 실행.
        // 뒷 방향 좌표.
        nextX = cx + dx[(cd + 2) % 4];
        nextY = cy + dy[(cd + 2) % 4];
        if (map[nextY][nextX] === 1) { // 정지.
          map2[nextY][nextX] = 9;
          return answer;
        } else {
          q.push(nextX, nextY, cd); // 뒤로 한 칸 후진한다.
          break;
        }
      }
      cnt++;
    }
  }

  return answer;
}
function main() {
  let v = new Array(N).fill(null).map(_ => new Array(M).fill(false));
  let map = input.slice(2).map(_ => _.toString().trim().split(' ').map(Number));
  let map2 = input.slice(2).map(_ => _.toString().trim().split(' ').map(Number));
  const [r, c, d] = input[1].split(' ').map(Number); // r=y,c=x,방향. (y,x,d);

  console.log(sol(r, c, d, map, v, map2));
}
main();

map2는 탐색 과정이 궁금해서 썼던 배열이므로 필요 없다.

 

특이사항

 문제의 조건을 잘 읽어보자.