[백준 - 13549, G5] 숨바꼭질 3 (JavaScript)

문제 설명[링크]

풀이 1(bfs)

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let [N, K] = input[0].split(' ').map(Number);

const visit = (pos, queue, visited) => {
  visited[pos] = true;
  queue.push(pos);
};

if (N >= K) {
  console.log(N - K);
} else {
  const maxSize = K * 2 + 1;
  const visited = new Array(maxSize).fill(false);

  let result = 0;
  let queue = [N];
  visited[N] = true;

  while (queue.length) {
    const newQueue = [];
    let isBreak = false;

    for (const pos of queue) {
      if (pos === K) {
        isBreak = true;
        break;
      }

      if (pos !== 0) {
        let posCache = pos * 2;

        while (posCache < maxSize) {
          if (!visited[posCache]) {
            visit(posCache, queue, visited);
          }

          posCache *= 2;
        }
      }
    }

    for (const pos of queue) {
      if (pos + 1 < maxSize && !visited[pos + 1]) {
        visit(pos + 1, newQueue, visited);
      }

      if (pos - 1 >= 0 && !visited[pos - 1]) {
        visit(pos - 1, newQueue, visited);
      }
    }

    if (isBreak) break;

    result += 1;

    queue = newQueue;
  }

  console.log(result);
}

결과 1

풀이 2(bitmasking)

const fs = require('fs');

const input = fs.readFileSync(
  process.env.LOGNAME === 'jake' ? './input.txt' : '/dev/stdin',
).toString().trim().split('\n');

let [N, K] = input[0].split(' ').map(Number);

if (N >= K) {
  console.log(N - K);
} else {
  let result = 0;

  if (N === 0) {
    result += 1;
    N += 1;
  }

  const getCount = (num, length) => {
    let count = 0;

    const prefix = num >> (length - 1);

    count += prefix;

    num ^= (prefix << (length - 1));

    while (num) {
      while (!(num & 1)) {
        num >>= 1;
      }

      if ((num & 2)) {
        num += 1;
      }

      num >>= 2;
      count += 1;
    }

    return count;
  };

  let length = 1;
  while (N < K) {
    length += 1;
    N <<= 1;
  }

  const num1 = N - K;
  const num2 = K - (N >> 1);

  const count1 = getCount(num1, length);
  const count2 = getCount(num2, length - 1);

  console.log(result + Math.min(count1, count2));
}

결과 2