[백준] 1697번: 숨바꼭질 - Node.js (자바스크립트)

1. 문제

1697번: 숨바꼭질

 

2. 풀이 

const [subin, sister] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(val => +val);
const visited = Array.from({ length: 100100 }, () => false);

const bfsMoveSubin = N => {
  const queue = [[N, 0]];
  visited[N] = true;

  while (queue.length) {
    const [subinCurrent, time] = queue.shift();

    if (subinCurrent === sister) return time;

    [subinCurrent - 1, subinCurrent + 1, subinCurrent * 2].forEach(possibility => {
      if (!visited[possibility] && possibility >= 0 && possibility <= 100000) {
        visited[possibility] = true;

        queue.push([possibility, time + 1]);
      }
    });
  }
};

console.log(bfsMoveSubin(subin));

 

2-1. 풀이 설명 

수빈이는 1초 마다 N + 1, N - 1, or N * 2 칸으로 이동할 수 있다. 문제의 핵심은 현재 수빈의 위치에서 동생의 위치까지 가기 위해서 어떤 조합으로 가야 가장 효율적인지 찾는 것이다. 

 

BFS 탐색으로 현재 수빈의 위치를 기준으로, 각 N + 1, N - 1, or N * 2 칸을 탐색하고 동생의 위치와 일치한지 확인한다. 맞는 경우 현재까지 누적된 시간 값을 반환하고, 아니라면 다시 현재 값을 기준으로 N + 1, N - 1, or N * 2 칸을 탐색한다.