[백준] 1963 소수 경로 Node.js (BFS 풀이)

Janet·2023년 6월 5일
0

Algorithm

목록 보기
213/314

문제

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

  • “이제 슬슬 비번 바꿀 때도 됐잖아”
  • “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
  • “그럼 8179로 해”
  • “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
  • “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
  • “귀찮아”

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

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

예제 입력 1

3
1033 8179
1373 8017
1033 1033

예제 출력 1

6
7
0

문제풀이

💡 문제풀이 과정

  • 네 자리의 숫자를 반복문을 돌면서 한 자리씩 0~9를 대입하여야 한다.
    • 숫자가 아닌 문자열로 만들고, 문자열에서 특정 인덱스의 문자를 변환하기 위해 slice()를 활용한다.
  • 소수인지 판별하는 함수를 작성하는데, 검사할 자연수의 제곱근 이하의 수까지만 검사를 하면 검사 범위를 줄일 수 있다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
let visited = []; 
let changed = [];
let startNum, goalNum;

// 문자열에서 특정 인덱스의 문자 변환하는 함수
String.prototype.replaceAt = function (index, replacement) {
  return this.slice(0, index) + replacement + this.slice(index + replacement.length);
};

// 소수 판별하는 함수
const isPrime = (N) => {
  for (let i = 2; i <= Math.sqrt(N); i++) {
    if (N % i == 0) return false;
  }
  return true;
};

const bfs = (start, goal) => {
  const queue = [start];
  visited[start] = true;
  changed[start] = 0; // BFS 시작 시 변경 횟수 0으로 저장

  while (queue.length) {
    const curNum = queue.shift();

	// 네 자리 문자열을 하나씩 0~9로 변경하기위한 중첩 반복문
    for (let idx = 0; idx < 4; idx++) {
      for (let num = 0; num < 10; num++) {

		// 다음 번호 = 현재 번호를 한 자리씩 0~9로 변경한 값
        const nextNum = curNum.replaceAt(idx, String(num));

		// 해당 번호(다음 번호)가 네 자리 범위를 벗어나거나, 방문한 번호이거나, 소수가 아니면 패스
        if (nextNum < 1000 || nextNum > 9999 || visited[nextNum] || !isPrime(nextNum)) continue;

        visited[nextNum] = true; // 방문 체크
        changed[nextNum] = changed[curNum] + 1; // 변경 횟수 = 기존 횟수 + 1
        queue.push(nextNum); // 해당 번호 큐에 담기

        if (nextNum == goal) return; // 해당 번호가 목표 번호에 도달하면 리턴
      }
    }
  }
};

for (let i = 1; i < input.length; i++) {
  [startNum, goalNum] = input[i].split(' '); // [시작 비밀번호, 목표 비밀번호]

  visited = Array(10000).fill(false); // 방문을 표시할 배열
  changed = Array(10000).fill(-1); // 비밀번호 변경 횟수를 표시할 배열 (초기값: -1)

  bfs(startNum, goalNum); // BFS 실행

  // 목표 비밀번호에 도달하기까지의 변경 횟수가 없다면 'Impossible'출력, 있다면 변경 횟수 출력
  console.log(changed[goalNum] == -1 ? 'Impossible' : changed[goalNum]);
}
profile
😸

0개의 댓글