[BOJ 1697] 숨바꼭질

문제

숨바꼭질

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

 

 

풀이

설명

수빈이가 동생을 찾는 가장 빠른 시간을 구하는 문제입니다.

 

BFS를 이용해 해결할 수 있습니다.

 

현재 위치를 cx라고 한다면,

다음 위치는 cx - 1, cx + 1 또는 2 * cx입니다.

 

예시 코드

function solution() {
  const [n, k] = input().split(" ").map(Number);
  if (k <= n) return n - k;

  const LIMIT = 100000;

  const dist = Array(LIMIT + 1);
  const queue = new Queue();
  dist[n] = 0;
  queue.enqueue(n);

  while (!queue.isEmpty()) {
    const cx = queue.dequeue();
    if (cx === k) return dist[cx];

    const nexts = [cx - 1, cx + 1, 2 * cx];
    for (const next of nexts) {
      if (next < 0 || next > LIMIT) continue;
      if (dist[next]) continue;

      dist[next] = dist[cx] + 1;
      queue.enqueue(next);
    }
  }
}