[백준] 1697 숨바꼭질 - javascript

📌 문제

https://www.acmicpc.net/problem/1697

📌 풀이

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0].split(" ")[0]);
let k = Number(input[0].split(" ")[1]);
let ch = new Array(100001).fill(0);
let ans = 0;
function BFS() {
  let queue = [];
  queue.push(n);
  ch[n] = 1;
  let cnt = 0;
  while (queue.length) {
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let x = queue.shift();
      if (x === k) return cnt;
      for (let nx of [x - 1, x + 1, x * 2]) {
        if (nx >= 0 && nx <= 100000 && ch[nx] === 0) {
          ch[nx] = 1;
          queue.push(nx);
        }
      }
    }
    cnt++;
  }
}
ans = BFS();
console.log(ans);

✔ 알고리즘 : BFS

✔ 수빈이는 +1 -1 *2 세가지 경로로 움직일 수 있으므로 큐에 넣을 때 3개를 각각 넣어준다

✔ 처음으로 위치가 k인 경우가 동생에게 갈 수 있는 최소 이동 횟수

✔ 시간단축을 위해 ch배열을 만들어 이미 갔던 지점은 가지 않는다

❗ 주의할 점
bfs함수 안에서 shift()하고 검사를 하지 않고 큐에 3가지 경로를 넣을 때 위치를 동생의 위치와 비교하면 이동횟수 없이 현재 동생과 수빈이의 위치가 같을 때 답이 0이 안나온다. 따라서 맨 처음에 큐에서 shift()로 뽑을 때 위치비교를 해줘야 한다

✔ 난이도 : 백준 기준 실버 1