소수 경로 [백준 1963][JAVA][골드5][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

https://www.acmicpc.net/problem/1963

1963번: 소수 경로

1. 참고사항 

- 1000의 자리는 1이하로 내려가면 안된다
- 각각의 자리수를 하나씩 바꿔야 한다.
- 소수면서 중복되지 않은 수를 탐색한다.

2. 구현

- 들어온 숫자를 자리수별로 char로 저장한다
- 숫자를 하나씩 바꿔가면서 방문하지 않은 곳이면서 소수이면 bfs를 돌린다
- 소수를 구하는 방법은 제곱근을 구해서 제곱근으로 나누어지면 소수가 아니다.
- 값을 찾으면 값을 출력하고 찾지 못하면 Impossible을 출력한다.

package Study6;

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

class Prime{
	int n;
	int cnt;
	public Prime(int n , int cnt) {
		this.n = n;
		this.cnt = cnt;
	}
}
public class 소수경로 {

	static int T,N;
	static boolean visit[];
	static Queue<Prime> q;
	static int from;
	static int to;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
		
		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to   = Integer.parseInt(st.nextToken());
			
			visit = new boolean[10001];
			q = new LinkedList<>();
			
			bfs();
		}
	}
	private static void bfs() {
		q.add(new Prime(from,0));
		
		if(from == to){
			System.out.println(0);
			return;
		}
		
		while(!q.isEmpty()) {
			Prime prime = q.poll();
			if(!visit[prime.n]) {
				visit[prime.n] = true;
				
				char[] numbers = Integer.toString(prime.n).toCharArray();
				
				for (int i = 0; i <= 9; i++) {
					for (int j = 0; j < 4; j++) {
						if(j == 0 && i == 0) continue;
						char origin = numbers[j];
						
						numbers[j] = (char)(i+'0');
						int n = Integer.parseInt(String.valueOf(numbers));
						numbers[j] = origin;
						
						if(visit[n]) continue;
						if(check(n)) {
							if(n == to){
								System.out.println(prime.cnt+1);
								return;
							}
							q.add(new Prime(n, prime.cnt+1));
						}
					}
				}
			}
		}
		System.out.println("Impossible");
	}
	
	private static boolean check(int n) {
		for (int i = 2; i <= (int)Math.sqrt(n); i++) {
			if(n%i == 0)
				return false;
		}
		return true;
	}

}