문제
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 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]);
}