[백준] 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을 출력한다.

 

해결방법 > 

네자리 소수 두개가 주어졌을 때, 첫번째 소수에서 두번째 소수까지의 최단 거리를 구하는 문제로 BFS(너비우선탐색) 알고리즘으로 해결.

 

일단은 네자리로 만들 수 있는 소수를 모두 찾는다.

 

첫번째 소수를 시작으로 인접한 소수를 탐색하는데 이 때 인접한 소수란 네자리 수 중에서 숫자 하나만 차이가 나는 소수이다.

 

인접한 소수들을 계속해서 너비우선탐색해서 두번째 소수가 나올때까지 탐색을 하고, 최단거리를 구한다.

 

[JAVA]

package baekjoon;

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

public class BOJ_1963 {
	static ArrayList <Integer> p = new ArrayList<>();
	public static int solve(int x, int y) {
		int answer = -1;
		Queue <Integer> q = new LinkedList<>();
		int[] visit = new int[10000];
		q.add(x);
		visit[x] = 1;
		
		while(!q.isEmpty()) {
			int nx = q.poll();
			String num1 = String.valueOf(nx);
			if(nx == y) {
				answer = visit[nx] - 1;
				break;
			}
			for(int i = 0; i < p.size(); i++) {
				if(visit[p.get(i)] == 0) {
					String num2 = String.valueOf(p.get(i));
					int cnt = 0;
					for(int j = 0; j < 4; j++) {
						if(num1.charAt(j) != num2.charAt(j)) cnt++;
					}
					if(cnt == 1) {
						q.add(p.get(i));
						visit[p.get(i)] = visit[nx] + 1;
					}
				}
			}
		}
		
		return answer;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		for(int i = 1000; i < 10000; i++) {
			int flag = 0;
			for(int j = 2; j <= Math.sqrt(i); j++) {
				if(i % j == 0) {
					flag = 1;
					break;
				}
			}
			if(flag == 0) p.add(i);
		}
		int tc = Integer.parseInt(tk.nextToken());
		for(int t = 0; t < tc; t++) {
			tk = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(tk.nextToken());
			int y = Integer.parseInt(tk.nextToken());
			int r = solve(Math.min(x, y), Math.max(x, y));
			if(r == -1) System.out.println("Impossible");
			else System.out.println(r);
		}
	}
}