Baekjoon 1963 소수 경로 JAVA

1963번: 소수 경로

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 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. 비밀번호로 사용가능 한 값은 1000~9999임.

2. 먼저 에라토스테네스의 체를 이용하여 10000까지의 수에서 소수판별을 한다.

3. BFS를 이용하여 각 자리의 값을 바꿔가면서 값을 탐색을 한다.

 => BFS의 특성으로 가장 먼저 나오는 값은 가장 빠른 탐색수를 가진다.

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		boolean [] Prime=new boolean [10001];
		for(int i=2;i<=100;i++) {
			for(int j=2;i*j<10000;j++)
				Prime[i*j]=true;
		}
		for(int t=0;t<T;t++) {
			int ans=0;
			boolean [] visited = new boolean[10001];
			StringTokenizer st = new StringTokenizer(br.readLine());
			Queue<int[]>q = new LinkedList<>();
			int a = Integer.parseInt(st.nextToken()), b=Integer.parseInt(st.nextToken());
			q.add(new int[] {a, 0});
			visited[a]=true;
			while(q.size()>0) {
				int [] temp = q.poll();
				int cur = temp[0], cnt=temp[1];
				if(cur==b) {
					ans=cnt;
					break;
				}
				for(int i=0;i<4;i++) {
					cur=temp[0];
					int tmp=(cur% (int)Math.pow(10, i+1))/(int)Math.pow(10, i);
					cur-=tmp*(int)Math.pow(10, i);
					for(int j=0;j<10;j++) {
						if(cur>=1000 && cur<10000 && !visited[cur] && !Prime[cur]) {
							q.add(new int[] {cur, cnt+1});
							visited[cur]=true;
						}
						cur+=Math.pow(10, i);						
					}
				}
			}
			if(visited[b])
				System.out.println(ans);
			else
				System.out.println("Impossible");
		}
	}
}