LeetCode 752 - Open the Lock (Medium)

문제

LeetCode - 752번

풀이 과정

문자열을 기준으로 특정 숫자에 도달하기 위한 최소 회전수를 구하는 문제입니다.

각 숫자에 대해서 증가하거나 감소할 수 있으며 deadends 에 포함되지 않는 숫자에 대해서만 탐색을 진행합니다.
따라서 조건에 맞도록 BFS 를 수행하며 목표 숫자에 도달하기 위한 최소 횟수를 구하면 됩니다.

코드

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
  const digits = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"];

  function bfs(start) {
    if (deadends.includes(start)) return -1;

    q = [];
    visit = new Array(10000).fill(false);

    q.push([start, 0]);
    visit[+start] = true;

    while (q.length) {
      const [here, cost] = q.shift();
      if (here === target) return cost;

      for (let i = 0; i < 4; i++) {
        let digit = +here[i];

        const prevDigitIdx = digit - 1 < 0 ? 9 : digit - 1;
        const nextDigitIdx = (digit + 1) % 9;

        const prevDigit = `${digits[prevDigitIdx]}`;
        const nextDigit = `${digits[nextDigitIdx]}`;

        [prevDigit, nextDigit].forEach((newDigit) => {
          const there = here.slice(0, i) + newDigit + here.slice(i + 1);
          if (!deadends.includes(there) && !visit[+there]) {
            q.push([there, cost + 1]);
            visit[+there] = true;
          }
        });
      }
    }

    return -1;
  }

  const answer = bfs("0000");
  return answer;
};