[백준] 1963 소수 경로

문제

---

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

 

 

 

 

풀이

---

우선 에라토스테네스의 체를 이용하여 소수를 찾아준다.

	
static void setPrimeNumber() {
	primeNumber = new boolean[10000];
	
	for(int i = 2 ; i * i < 10000 ; i++) {
		if(primeNumber[i]) { 
			continue;
		}
		
		for(int j = i * i; j < 10000; j += i) {
			primeNumber[j] = true;
		}			
	}
	
	return;
}

 

 

우선 자릿수 한개만 바꿔줄 수 있으므로 한 자릿수씩 바꾸면서 BFS 방식으로 문제를 풀어주었다.

한자릿수씩 바꿔주는 건 수학적으로 첫번째자리면 1씩더해주거나 빼주고 두번째자리라면 10씩더해주거나 빼주고 .. 같은 방식을 네번째 자시수까지 해주면 된다.

static int solution(int origin, int goal) {
	
	
	Queue<node> queue = new LinkedList<>();
	queue.add(new node(origin, 0));
	visited[origin] = true;
	
	while(!queue.isEmpty()) {
		
		node now = queue.poll();
	
		if(now.number == goal) {
			return now.times;
		}
		
		for(int i = 3 ; i >= 0 ; i--) {
			
			int tmp = now.number;
			int num = now.number;
			
			int cnt = 0;
			while( cnt < i) {
				num /= 10;
				cnt++;
			}
			
			num %= 10;			
			
			for(int j = num + 1 ; j < 10 ; j++) {
				tmp += Math.pow(10, i);
				
				if(tmp > 10000) {
					break;
				}
				
				if(!primeNumber[tmp] && !visited[tmp]) {
					visited[tmp] = true;
					queue.add(new node(tmp, now.times + 1));
				}
			}
			
			tmp = now.number;
			for(int j = num - 1 ; j >= 0 ; j--){
				tmp -= Math.pow(10, i);
				
				if(tmp < 1000) {
					break;
				}
				
				if(!primeNumber[tmp] && !visited[tmp]) {
					visited[tmp] = true;
					queue.add(new node(tmp, now.times + 1));
				}
			}
		}			
	}

	return -1;
}

 

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static boolean[] primeNumber;
	static boolean[] visited;
		
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int testCase = parseInt(bufferedReader.readLine());
		
		setPrimeNumber();
		
		for(int i = 0 ; i < testCase ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			
			int origin = parseInt(st.nextToken());
			int goal = parseInt(st.nextToken());
			
			visited = new boolean[10000];
			int result = solution(origin, goal);
			
			if(result == -1) {
				sb.append("Impossible\n");
				
			}
			else {
				sb.append(result + "\n");
			}
			
		}
		
		System.out.println(sb);
	}
	
	static class node{
		int number;
		int times;
		
		node(int number, int times){
			this.number = number;
			this.times = times;
		}
	}
		
	static int solution(int origin, int goal) {
		
		
		Queue<node> queue = new LinkedList<>();
		queue.add(new node(origin, 0));
		visited[origin] = true;
		
		while(!queue.isEmpty()) {
			
			node now = queue.poll();
		
			if(now.number == goal) {
				return now.times;
			}
			
			for(int i = 3 ; i >= 0 ; i--) {
				
				int tmp = now.number;
				int num = now.number;
				
				int cnt = 0;
				while( cnt < i) {
					num /= 10;
					cnt++;
				}
				
				num %= 10;			
				
				for(int j = num + 1 ; j < 10 ; j++) {
					tmp += Math.pow(10, i);
					
					if(tmp > 10000) {
						break;
					}
					
					if(!primeNumber[tmp] && !visited[tmp]) {
						visited[tmp] = true;
						queue.add(new node(tmp, now.times + 1));
					}
				}
				
				tmp = now.number;
				for(int j = num - 1 ; j >= 0 ; j--){
					tmp -= Math.pow(10, i);
					
					if(tmp < 1000) {
						break;
					}
					
					if(!primeNumber[tmp] && !visited[tmp]) {
						visited[tmp] = true;
						queue.add(new node(tmp, now.times + 1));
					}
				}
			}			
		}
	
		return -1;
	}
	
	static void setPrimeNumber() {
		primeNumber = new boolean[10000];
		
		for(int i = 2 ; i * i < 10000 ; i++) {
			if(primeNumber[i]) { 
				continue;
			}
			
			for(int j = i * i; j < 10000; j += i) {
				primeNumber[j] = true;
			}			
		}
		
		return;
	}
}