소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.
3
1033 8179
1373 8017
1033 1033
6
7
0
💡 문제풀이 과정
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]);
}