링크

1963 소수 경로

문제

풀이

이 문제는 bfs를 통해 문제를 풀었다.
1. 4자리 번호가 있으면 한자리씩 0~9까지 바꾼다.
2. 바꾼 번호가 소수인지 체크한다.(천의 자리가 0이면 안된다.)
3. 소수이고 이전에 만든 숫자가 아니라면 queue에 넣어준다.

이렇게 반복해서 찾고자 하는 값과 같으면 return해서 풀었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Node{
	int count = 0;
	String currentWord = "";
	
	public Node(int count, String currentWord) {
		this.count = count;
		this.currentWord = currentWord; 
	}
}


public class Main {
	public static boolean[] visited = new boolean[10000];
	public static String dept = "Impossible";
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			String a = st.nextToken();
			String b = st.nextToken();
			
			dept = "Impossible";
			bfs(a, b);
			System.out.println(dept);
			
		}
		
	
		
	}
	
	public static void bfs(String a, String b) {
		Queue<Node> queue = new LinkedList<>();
		visited = new boolean[10000];
		queue.add(new Node(0, a));
		
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			
			if(node.currentWord.equals(b)) {
//				System.out.println(node.count);
				dept = String.valueOf(node.count);
				break;
			}
			
			for(int i=0;i<4;i++) {
//				System.out.println("i = " + i);
				for(int j=0;j<10;j++) {
					String word = node.currentWord;
					StringBuilder sb = new StringBuilder();
					for(int k=0;k<4;k++) {
						if(i == k) {
							sb.append(j);
						} else {
							sb.append(word.charAt(k));
						}
					}
					
					int intWord = Integer.parseInt(sb.toString());
					if(sb.charAt(0) - '0'!= 0 && !visited[intWord] && checkSosu(sb.toString())) {
//						System.out.println(intWord);
						visited[intWord] = true;
						queue.add(new Node(node.count + 1, sb.toString()));
					}
					
				}
			}
			
		}
		
		
	}
	
	
	
	public static boolean checkSosu(String word) {
		int element = Integer.parseInt(word);
		
		for(int i=2;i<=Math.sqrt(element);i++) {
			if(element % i == 0) return false;
		}
		
		return true;
	}
	
	
}