백준18112 - 이진수 게임 (비트마스킹 & BFS) node.js

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

해당 문제 역시 자바스크립트로 해결된 풀이가 없어 포스팅하게 되었다.

 

문제 풀이 방식

이진수와 비트마스킹에 대해 조금이라도 이해하고 있다면 풀이가 어렵지 않은 문제. 하지만, 항상 비트마스킹 연산자는 정확히 기억나지 않으니, 이전에 포스팅했던 내용을 참고했다. (기특해 과거의 나...)

2023.11.17 - [개발/Python | Java] - Python 문법 & 비트마스킹

 

해당 문제에서 가장 중요한 부분은 한 자리 숫자를 보수로 바꾸는 방식이기에 이에 대한 설명만 남긴다.

한 자리의 숫자를 보수로 바꾸는 연산은 연산자(^ XOR) 하나로 해결이 가능하다.

XOR 연산은 두 개의 비트가 서로 다를 때 1을 반환하는 연산이기 때문에, 원하는 위치의 비트를 반전시킬 수 있다.

// 11에서 2번째 비트의 보수를 변경하는 경우
11(1011) ^ (1 << 2) =>> 15(1111)

// 11에서 1번째 비트의 보수를 변경하는 경우
11(1011) ^ (1 << 1) =>> 9(1001)

// 11에서 0번째 비트의 보수를 변경하는 경우
11(1011) ^ (1 << 0) =>> 10(1010)

 

전체 소스 코드

추신, 대기열(queue) 을 통과한 원소를 상대로 중복처리를 할 경우 시간 초과로 정답 처리가 되지 않아, queue에 추가하기 전에 중복 여부를 확인하는 방식으로 로직을 작성했다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const [n, m] = data.map((el) => parseInt(el, 2));
  const queue = [[n, 0]];
  let queueIdx = 0;

  const visited = {};
  visited[n] = true;
  while (queueIdx < queue.length) {
    const [node, cnt] = queue[queueIdx++];
    if (node === m) {
      console.log(cnt);
      return;
    }

    for (let i = node.toString(2).length - 2; i >= 0; i--) {
      let newNode = node ^ (1 << i);

      // if ((node & (1 << i)) !== 1 << i) newNode = node | (1 << i); / 합연산
      // else newNode = node & ~(1 << i); / 차연산
      if (!visited[newNode]) {
        queue.push([newNode, cnt + 1]);
        visited[newNode] = true;
      }
    }

    if (!visited[node + 1]) {
      queue.push([node + 1, cnt + 1]);
      visited[node + 1] = true;
    }
    if (node && !visited[node - 1]) {
      queue.push([node - 1, cnt + 1]);
      visited[node - 1] = true;
    }
  }
}

solution(input);