[algorithm] 백준 1963 - 소수경로

[문제]
https://www.acmicpc.net/problem/1963

let input = require('fs').readFileSync('testcase.txt').toString().split('\n');

const eratos = new Array(9999).fill(true);
for (let i = 2; i * i < 10000; i++) {
  for (let j = 2*i; j < 10000; j += i) {
    eratos[j] = false;
  }
}

const bfs = (a, b) => {
  const queue = [];
  const visited = [];
  visited[a] = 0;
  queue.push(a);
  while(queue.length !== 0) {
    const tmp = queue.shift();
    if (tmp === b) {
      return visited[tmp];
    }
    for (let i = 0; i < 4; i++) {
      for (let j = 0; j < 10; j++) {
        let newTmp = tmp - Number(Math.floor(tmp / 10 ** (3 - i)).toString().slice(-1)) * 10 ** (3 - i) + j * 10 ** (3 - i);
        if (newTmp >= 1000 && eratos[newTmp] && typeof visited[newTmp] !== 'number') {
          visited[newTmp] = visited[tmp] + 1;
          queue.push(newTmp);
        }
      }
    }
  }
  return 'Impossible';
}

for (let i = 1; i <= T; i++) {
  let [curPwd, newPwd] = input[i].split(' ');
  curPwd = Number(curPwd);
  newPwd = Number(newPwd);
  console.log(bfs(curPwd, newPwd));
}

어려웠던 점

1. 에라토스테네스의 체 알고리즘
   이번 문제를 풀면서 에라토스테네스의 체 알고리즘을 처음 알게 됐고, 여기 저기 블로그들을 찾아보면서 공부를 했다.
   알고리즘을 구현한 코드를 적은 블로깅들 중에 틀린 부분이 있어서 헷갈렸다.

   const eratos = new Array(9999).fill(true);
   for (let i = 2; i * i < 10000; i++) {
     for (let j = 2*i; j < 10000; j += i) {
       eratos[j] = false;
     }
   }

2. visited 값을 설정하는 타이밍(코드 위치)를 잘못 잡아서 오랫동안 헤맸다.
   queue 에서 shift 한 tmp 값으로부터 숫자 한 개만 변경해서 얻을 수 있는 소수를 찾고, 그 소수의 visited 를 업뎃해주고 queue 에 넣어줘야 한다.

3. 하나의 자리만 바꾸어주는 코드

   let newTmp = tmp - Number(Math.floor(tmp / 10 ** (3 - i)).toString().slice(-1)) * 10 ** (3 - i) + j * 10 ** (3 - i);

   예를 들어 7281 에서 백의 자릿수자를 j로 변경하려고 할 때 7281을 100으로 나눈 값 72를 구하고 72를 문자로 바꾸어(String()) 마지막 문자막 취한 다음(slice(-1)), 그것을 다시 숫자로 바꿔주면(Number()) 백의 자릿수 2를 얻을 수 있다. 2 * 100 만큼 빼주고 j * 100 만큼 더해주면 7281은 7j81로 바뀌게 된다.