1963

소수 경로 : https://www.acmicpc.net/problem/1963

참조 : https://log-laboratory.tistory.com/113

 

여러모로 실수가 많았던 문제

 

에라토스테네스의 체를 구하고, visited 및 dp 배열 생성에는 크게 문제가 없었다.

그런데도 33%정도에서 계속 실패하는 이유를 알 수 없어 위의 사이트를 참조함.

 

//integer 상태에서 연산하는 것에 대한 연습이 부족함을 느낀다.

 

//자리수 별로 쪼개서 digits 배열에 저장

int tmp = value;
int[] digits = new int[4];
for (int j = 0; j < 4; j++) {
digits[j] = tmp / d[j];
tmp %= d[j];
}

 

 

//newNumber에 한자리씩 숫자를 변경하여 재조합

for (int j = 0; j < 4; j++) {
for (int k = 0; k < 10; ++k) {

digits[j] = (digits[j] + 1 > 9) ? 0 : digits[j] + 1;
int newNumber = 0;
for (int l = 0; l < 4; l++) {
newNumber += digits[l] * d[l];
}

}

}

 

 

*가장 치명적이었던 실수는 answer 를 매 TC마다 초기화 하지 않아 이상한 답이 나왔던 부분이다.

이런 실수 하면 안된다... 못찾는다

 

//참조코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int answer;
	static int N, K;
	static boolean DBG = false;
	static int[] dp;
	static boolean[] visited;
	static int[] d = { 1000, 100, 10, 1 };
	static boolean found;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		dp = new int[10000];

		for (int k = 2; k <= 9999; k++) {
			if (dp[k] == 0) {
				for (int h = k + k; h <= 9999; h = h + k) {
					dp[h] = 1;
				}
			}
		}

		for (int i = 0; i < N; ++i) {

			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			visited = new boolean[10000];
			found = false;
			answer = Integer.MAX_VALUE;
			bfs(a, b);
			if (found)
				System.out.println(answer);
			else
				System.out.println("Impossible");
		}

	}

	private static void bfs(int start, int target) {
		
		Queue<Integer> Q = new LinkedList<>();

		Q.offer(start);
		visited[start] = true;

		int level = 0;
		while (!Q.isEmpty()) {
			int len = Q.size();

			for (int i = 0; i < len; ++i) {
				int value = Q.poll();
				if (value == target) {
					//answer = level;
					answer = Math.min(answer, level);
					if (DBG)
						System.out.printf("[found]level : %d value : %d \n", level, value);
					found = true;
					return;
				}

				int tmp = value;
				int[] digits = new int[4];
				for (int j = 0; j < 4; j++) {
					digits[j] = tmp / d[j];
					tmp %= d[j];
				}

				for (int j = 0; j < 4; j++) {
					for (int k = 0; k < 10; ++k) {

						digits[j] = (digits[j] + 1 > 9) ? 0 : digits[j] + 1;
						int newNumber = 0;
						for (int l = 0; l < 4; l++) {
							newNumber += digits[l] * d[l];
						}

						if (newNumber < 1000)
							continue;
						if (dp[newNumber] == 1)
							continue;
						if (visited[newNumber])
							continue;

						visited[newNumber] = true;
						Q.offer(newNumber);
					}
				}
			}
			++level;
		}
		found = false;
	}
}​

 

//기존 작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int answer = Integer.MAX_VALUE;
	static int N, K;
	static boolean DBG = false;
	static int[] dp;
	static boolean[] visited;
	static boolean found;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		

		dp = new int[10000];
		
		for (int k = 2; k <= 9999; k++) {
			if (dp[k] == 0) {
				for (int h = k + k; h <=9999; h = h + k) {
					dp[h] = 1;
				}

				/*
				 * if( k >= a && k <= b) System.out.println(k);
				 */
			}

		}

		for (int i = 0; i < N; ++i) {
			
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			//init
			answer = Integer.MAX_VALUE;
			visited = new boolean[10000];
			found = false;
			bfs(a, b);		
			if(found)
				System.out.println(answer);
			else 
				System.out.println("Impossible");
				
			
		}

	}

	static boolean checkPrime(int num) {
		for (int i = 2; i * i <= num; i++) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}

	private static void bfs(int start, int target) {
		Queue<Integer> Q = new LinkedList<>();

		if (start == target) {
			answer = 0;
			found=true;
			return;
		}

		Q.offer(start);
		visited[start] = true;

		int level = 0;
		while (!Q.isEmpty()) {
			int len = Q.size();

			for (int i = 0; i < len; ++i) {
				int value = Q.poll();
				if (value == target) {
					answer = Math.min(answer, level);
					// System.out.printf("[found]level : %d value : %d \n",level, value);
					found=true;
					return;
				}
				for (int idx = 1000; idx < 10000; ++idx) {
					/* prime number */
					if (dp[idx] == 0 && !visited[idx]) {
						/* 한자리만 다른 경우 */
						String iStr = idx + "";
						String vStr = value + "";
						int cnt = 0;
						for (int o = 0; o < vStr.length(); o++) {
							if (iStr.charAt(o) != vStr.charAt(o))
								cnt++;
						}
						if (cnt >= 2)
							continue;
						if (cnt == 1) {
							visited[idx] = true;
							// System.out.printf("level : %d value : %d idx : %d\n",level, value, idx);
							Q.offer(idx);
						}
					}
				}
			}
			++level;
		}
	}
}