Article Image
Article Image
read
문제
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 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
풀이
이 문제는 소수의 여부를 체크하기 위해 에라토스테네스의 체를 이용했고 해당 숫자로 가기위한 최소 횟수를 구하기 위해 BFS 알고리즘을 이용해서 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static boolean[] flag;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
flag = new boolean[10000];
for(int i=2; i*i<10000; i+=1) {
for(int j=i*i; j<10000; j+=i) {
flag[j] = true;
}
}
for(int t=0; t<T; t++) {
String[] input = br.readLine().split(" ");
bfs(input[0], input[1]);
}
}
public static void bfs(String str, String target) {
Queue<Pair> queue = new LinkedList<>();
boolean[] visited = new boolean[10000];
queue.add(new Pair(str, 0));
visited[Integer.parseInt(str)] = true;
StringBuilder sb;
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(temp.str.equals(target)) {
System.out.println(temp.cnt);
return;
}
for(int i=0; i<4; i++) {
sb = new StringBuilder(temp.str);
for(int j=0; j<=9; j++) {
if(i==0 && j==0) continue;
char c = (char) (j+'0');
sb.setCharAt(i, c);
if(!flag[Integer.parseInt(sb.toString())] && !visited[Integer.parseInt(sb.toString())]) {
visited[Integer.parseInt(sb.toString())]=true;
queue.add(new Pair(sb.toString(), temp.cnt+1));
}
}
}
}
System.out.println("Impossible");
}
public static class Pair {
String str;
int cnt;
public Pair(String str, int cnt) {
this.str = str;
this.cnt = cnt;
}
}
}