송아지 찾기 : BFS (상태트리탐색)

풀이

function solution(s, e) {
  let answer = 0;
  const jump = Array.from({ length: 10001 }, () => 0);
  const check = Array.from({ length: 10001 }, () => 0);
  const mv = [1, -1, 5];
  const queue = [];

  let x = s;
  queue.push(x);
  check[x] = 1;

  while (queue.length) {
    x = queue.shift();
    if (x === e) return jump[x];
    for (dx of mv) {
      nx = x + dx;
      if (!check[nx] && 1 <= nx && nx <= 10000) {
        check[nx] = 1;
        jump[nx] = jump[x] + 1;
        queue.push(nx);
      }
    }
  }
  return answer;
}

console.log(solution(5, 14));

전에는 DFS 문제도 BFS로 풀 정도로 BFS를 좋아했는데... 며칠동안 계속 DFS 문제만 풀어서 그런지 BFS 문제푸는게 어색한 것 같다 ㅠㅠ
이 단순한 문제를 푸는 데에도 한참 걸렸다
그냥 단순 BFS 구현 문제들은 그냥 꼭꼭 씹어서 암기를 해버려야 겠다....

Solution 풀이 2 - level을 이용한 풀이

function solution(s, e) {
  const check = Array.from({ length: 10010 }, () => false);
  const queue = [];
  const mv = [1, -1, 5];

  queue.push(s);
  check[s] = 1;
  let level = 0;

  while (queue.length) {
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let x = queue.shift();
      if (x === e) return level;
      for (let d of mv) {
        const nx = x + d;
        if (0 < nx && nx <= 10000 && !check[nx]) {
          check[nx] = 1;
          queue.push(nx);
        }
      }
    }
    level++;
  }
}

console.log(solution(8, 3));

• len을 따로 선언하지 않아서 엄청 애먹었다...
  for문이 돌 때마다 queue.length 의 값이 변한다는 것을 몰랐다 ㅠㅠ
• 풀이1보다 훨씬 직관적으로 level의 계층 구조를 파악할 수 있는 풀이인 것 같다(메모리도 더 아낄 수 있고 !)