[BOJ] 숨바꼭질 | BFS

Problem | 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

Input | 5 17
Output | 4

✨ 접근 방식

BFS를 통해 레벨을 체크한다. (레벨 = 가장 빠른 시간)

BFS는 이미 방문했는지 체크하는 체크 배열, queue가 필요하다.

• queue.length!=0 때만큼 while문을 돌면서 그 안에서 또 for문으로 queue.length 만큼 순회해준다. (각 레벨의 요소들을 모두 push 해주기 위해)
  • for문을 돌 때, 찾으려는 수를 찾으면 바로 값을 return 해준다.

- ✔️ 전체코드

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
// n=수빈이 있는 위치
// k= 동생이 있는 위치

let n = Number(input[0].split(" ")[0]);
let k = Number(input[0].split(" ")[1]);

function solution(n, k) {
  let queue = [];
  let checked = new Array(100001).fill(0);
  let L = answer =0;
  function BFS() {
    // 1. 먼저 초기 설정  -> 5를 넣어준다.
    queue.push(n);
    checked[n] = 1;
    while (queue.length) {
      let len = queue.length;
      for (let i = 0; i < len; i++) {
        let x = queue.shift();
        if (x === k) return L;
        for (let nv of [x - 1, x + 1, x * 2]) {
          if (checked[nv] === 0 && nv >= 0 && nv <= 100000) {
            queue.push(nv);
            checked[nv] = 1;
          }
        }
      }
      L++;
    }
  }

  if (n === k) return 0;
  else {
    answer = BFS();
    return answer;
  }
}
console.log(solution(n, k));

- 🔥 필요한 기능들

for (let nv of [x - 1, x + 1, x * 2]) : 이동하는 만큼, for문을 돈다.