[BOJ] 1963 소수 경로 (node.js)

BOJ 문제 1963번의 풀이 과정을 작성한 게시글입니다.

 

링크

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

 

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데.

 

“이제 슬슬 비번 바꿀 때도 됐잖아”

“응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"

“그럼 8179로 해”

“흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”

“흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”

“귀찮아”

 

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

 

풀이 과정

접근법 : 에라토스테네스의 체 + BFS

후보 숫자가 4자리 수이기 때문에 최소 1000 ~ 최대 9999라고 치면 전체 탐색해야 할 숫자는 최대 9000개이다.

하지만 매 테스트 케이스마다 소수 여부를 판정하면 테스트 케이스 수 만큼 연산을 수행해야 하기 때문에, 미리 1000~9999까지 소수인지의 여부를 판단한 후에 각 테스트 케이스에 대해 두 소수 사이의 변환에 필요한 최소 횟수를 구한다.

 

두 소수 사이의 최소 변환 횟수를 구해야하기 때문에 최단 경로 알고리즘인 bfs로 구해준다.

 

코드

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

const prime = Array.from({ length: 10001 }, () => true);

prime[1] = false;

for (let i = 2; i <= 100; i++) {
  for (let j = i * 2; j <= 10000; j += i) {
    prime[j] = false;
  }
}

const answer = [];

for (let i = 0; i < T; i++) {
  const [f, t] = input[i].split(" ").map(Number);
  const visited = Array.from({ length: 10001 }, () => false);
  const queue = [];

  queue.push([f, 0]);
  visited[f] = true;

  while (queue.length > 0) {
    const [num, cnt] = queue.shift();

    if (num === t) {
      answer.push(cnt);
      break;
    }

    for (let i = 0; i < 4; i++) {
      const prev = String(num).split("");
      for (let j = 0; j <= 9; j++) {
        if (prev[i] === j) continue;

        prev[i] = j;

        const next = +[...prev].join("");

        if (next < 1000 || visited[next] || !prime[next]) continue;

        visited[next] = true;
        queue.push([next, cnt + 1]);
      }
    }
  }
}

console.log(answer.join("\n"));

 

후기

다양한 알고리즘을 조합해야 하는 문제이다.

일반적인 문제와는 다른 아이디어를 요구한다.