[백준20304_자바스크립트(javascript)] - 비밀번호 제작

🔴 문제

비밀번호 제작

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path, 'utf-8').trim().split('\n');
const n = Number(inputs[0]);
const m = Number(inputs[1]);
const logs = inputs[2].split(' ').map(Number);
const visited = new Array(n + 1).fill(false);

const q = logs.map((it) => [it, 0]);
let maxSafety = 0;
let front = 0;
logs.forEach((log) => (visited[log] = true));

while (front < q.length) {
  const [log, safety] = q[front++];

  if (maxSafety < safety) maxSafety = safety;

  for (let i = 0; i < 20; i++) {
    const nLog = log ^ (1 << i);

    if (nLog > n || visited[nLog]) continue;

    visited[nLog] = true;
    q.push([nLog, safety + 1]);
  }
}

console.log(maxSafety);

🟢 풀이

⏰ 소요한 시간 : -

처음에 입력받은 수를 이진수로 바꾸고 완전탐색을 돌리며 난리를 쳤는데 구현하다 보니 이 데이터 양으로는 아무리 봐도 1초 안에 완탐이 불가능했다.
그래서 질문게시판을 봤더니 비트마스킹 기법이라 해서 유튜브로 비트연산 복습부터 했다.

그 다음 지피티한테 조언을 요청했다... ㅋㅋ 핵심아이디어를 봐도 감이 잘 잡히지 않았는데 풀이를 자세히 적어주신 블로그도 봐서 참고했다.

각 비밀번호별로 한자리씩만 어떻게 바꿔야 하지 ? 라 생각했는데 1과 XOR 연산을 사용하면 쉽게 구할 수 있었다.

• 3 : 0011
• 3 ^ (1<<0) : 0011^0001 = 0010
• 3 ^ (1<<1) : 0011^0010 = 0001
• 3 ^ (1<<2) : 0011^0100 = 0111
• 3 ^ (1<<3) : 0011^1000 = 1011

그래서 입력받은 로그인 시도에 사용된 비밀번호에 XOR 연산을 적용하여 가능한 모든 경우의 수를 구한다. 모든 경우의 수를 탐색하면서 범위를 벗어나거나 이미 방문한 노드라면 종료한다. 큐에 추가될 때, safety 는 1씩 증가하고 이 값이 안전도가 되니까 이 안전도로 최대값을 구해 정답을 출력하면 된다.
탐색의 범위가 매우 크므로 큐에서 맨 앞의 요소를 빼올때 shift()가 아닌 index로 접근한다.

알게된 점
1. 정수는 내부적으로 이진수로 저장되기 때문에 문자열이나 배열로 바꾸어 주지 않아도 비트연산이 가능하다.
2. 비트마스킹 기법

🔵 Ref

https://www.youtube.com/watch?v=yHBYeguDR0A
https://kwanik.tistory.com/33
https://claude.ai/