🔍 문제
💻 제출
📌 입력
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
📌 출력
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.
🤔 생각
해당 문제를 봤을 때 4자리 수에 해당하는 모든 수를 배열에 저장 해놓고 password 변경 시에
배열에 속하는 숫자인지 확인 하는 식으로 풀이 하기로 했다.
ArrayList<Integer> primeNum 를 선언 하고 isPrime 함수를 통해 1000 ~ 9999 까지 소수를 판별 한다.
static boolean isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) { //제곱근 까지만 순회해도 소수 판별 가능
if (num % i == 0) {
return false;
}
}
return true; //소수 임
}전체 숫자를 순회 해도 상관 없지만 주어진 숫자의 제곱근 까지만 순회 해도 소수는 판별이 가능 하다.
배열 안에 모든 4자리 숫자가 저장 되었다면 각 자리 비밀번호를 변경 하면서 BFS탐색을 진행 한다.
📝 코드
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int T, S, E;
static ArrayList<Integer> primeNum = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine());
for (int i = 1000; i <= 9999; i++) { //4자리 수 시작
if (isPrime(i) == true) {
primeNum.add(i);
}
}
for (int t = 0; t < T; t++) {
StringTokenizer stL = new StringTokenizer(br.readLine(), " ");
S = Integer.parseInt(stL.nextToken()); // 시작 번호
E = Integer.parseInt(stL.nextToken()); // 타겟 번호
if (S == E){
bw.write("0\n");
continue;
}
int depth = bfs(S);
bw.write(depth != -1 ? (depth + "\n") : "Impossible\n");
}
bw.flush();
bw.close();
}
static boolean isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) { //제곱근 까지만 순회해도 소수 판별 가능
if (num % i == 0) {
return false;
}
}
return true; //소수 임
}
static int bfs(int start) {
//시작 숫자가 소수 배열 몇번째 index 를 가지는지 확인
int findIdx = primeNum.indexOf(start);
int depth = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(findIdx);
boolean[] visited = new boolean[primeNum.size()];
visited[findIdx] = true;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
Integer cIdx = q.poll(); //현재 비밀번호 index
int nowP = primeNum.get(cIdx); //현재 비밀번호 값
if (nowP == E) { //찾았다면
return depth;
}
//천의 자리수 변경
for (int i = 1; i < 10; i++) { //1 ~ 9
int nextP = (i * 1000) + (nowP % 1000);
if (primeNum.contains(nextP) && nextP != nowP) {
//바뀐 숫자가 소수 여야함
//바뀌기 전 숫자와 달라야 함
int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
if (visited[nextIdx] == false) {
q.offer(nextIdx);
visited[nextIdx] = true;
}
}
}
//백의 자리 수 변경
for (int i = 0; i < 10; i++) { //0 ~ 9
int nextP = ((nowP / 1000) * 1000) + (i * 100) + (nowP % 100);
if (primeNum.contains(nextP) && nextP != nowP) {
//바뀐 숫자가 소수 여야함
//바뀌기 전 숫자와 달라야 함
int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
if (visited[nextIdx] == false) {
q.offer(nextIdx);
visited[nextIdx] = true;
}
}
}
//십의 자리 수 변경
for (int i = 0; i < 10; i++) { //0 ~ 9
int nextP = ((nowP / 100) * 100) + (i * 10) + (nowP % 10);
if (primeNum.contains(nextP) && nextP != nowP) {
//바뀐 숫자가 소수 여야함
//바뀌기 전 숫자와 달라야 함
int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
if (visited[nextIdx] == false) {
q.offer(nextIdx);
visited[nextIdx] = true;
}
}
}
//일의 자리 수 변경
for (int i = 0; i < 10; i++) { //0 ~ 9
int nextP = ((nowP / 10) * 10) + i;
if (primeNum.contains(nextP) && nextP != nowP) {
//바뀐 숫자가 소수 여야함
//바뀌기 전 숫자와 달라야 함
int nextIdx = primeNum.indexOf(nextP); //바뀐 숫자 Index
if (visited[nextIdx] == false) {
q.offer(nextIdx);
visited[nextIdx] = true;
}
}
}
}
depth++;
}
return -1;
}
}📗 정리
원래는 password가 주어진다면 소수 배열에서 해당 숫자의 index를 찾아낸 후 index를 +1 , -1 해주면서 BFS 탐색을 하려 했다.
하지만 위와 같이 탐색을 진행 하는 경우 1의 자리부터 순차적으로 값을 변경 하면서 depth를 증가 시키기 때문에 예제에서 원하는 return 값을 절대로 받아 낼 수 없다.
단순히 가능한지 여부만 판단한다면 가능 할 수도 있겠다.
따라서 각 자리 숫자 변경을 통해서 변경 된 수를 큐에 넣어주면서 경우의 수를 탐색 했다.
기존 접근 했던 숫자는 visited배열을 통해 중복 접근 하지 못하게 설정 해 주었다.
wkd86591247@gmail.com