[백준_1697] 숨바꼭질 ( by using JavaScript )

문제

 

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

1697번: 숨바꼭질

 

How to Solve ?

 

[1] BFS

 

이 문제를 풀면서, 이게 과연 "BFS" 의 특징을 잘 살린걸까? 라는 의문을 가졌고 실제로도 visited 없이도 정답이 출력이 된다. 하지만, 방문 여부를 체크 하게 되면 불필요한 순회를 제거 할 수 있기에 사용 할 가치는 있다고 생각 !

function solution() {
  let count = 0;
  const visited = Array(100001).fill(false);
  const queue = [[N, count]];

  while (queue.length) {
    const [start, count] = queue.shift();

    if (visited[start]) {
      continue;
    }

    visited[start] = true;

    if (start === K) {
      return count;
    }

    if (start * 2 <= 100000) {
      queue.push([start * 2, count + 1]);
    }

    if (start + 1 <= 100000) {
      queue.push([start + 1, count + 1]);
    }

    if (start - 1 >= 0) {
      queue.push([start - 1, count + 1]);
    }
  }
}

let N = 5;
let K = 17;

console.log(solution(N, K));