송아지 찾기(BFS)

문제

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아
지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음
과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.
현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수
있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성
하세요.

제한 사항

입출력 예

풀이

function solution2(n, s) {
  let check = new Array(10001).fill(0);
  let dis = new Array(10001).fill(0);
  let queue = [];
  check[n] = 1;
  queue.push(n);

  while (queue.length) {
    let current = queue.shift();
    for (let next of [current + 1, current - 1, current + 5]) {
      if (next === s) {
        return dis[current] + 1;
      }
      if (next >= 0 && next <= 10000 && !check[next]) {
        check[next] = 1;
        queue.push(next);
        dis[next] = dis[current] + 1;
      }
    }
  }
}
console.log(solution2(5, 14));

• 최소 문제는 bfs로 풀 수 있다.
• dis배열을 사용한 레벨 추적하는 테크닉을 기억하자!

function solution2(n, s) {
  let check = new Array(10001).fill(0);
  let queue = [];
  check[n] = 1;
  queue.push([n, 0]);

  while (queue.length) {
    let [current, cnt] = queue.shift();
    for (let next of [current + 1, current - 1, current + 5]) {
      if (next === s) {
        return cnt + 1;
      }
      if (next >= 0 && next <= 10000 && !check[next]) {
        check[next] = 1;
        queue.push([next, cnt + 1]);
      }
    }
  }
}
console.log(solution2(5, 14));

• dis 배열을 이용한 추적이 아닌 queue에 넣을 때 변수하나를 더 넣어서 count 해줄 수 있다.