[BOJ/JAVA] 백준 1963번 : 소수 경로

1963번: 소수 경로

 

 

 

---

 

 

 

• 생각

 

testcase만큼 4자리인 왼쪽 수를 오른쪽 수로 한자리씩 소수로만 만들면서 변경해야한다.

 

dfs방식으로 basecase를 왼쪽 수와 오른쪽 수가 같아질때로 만든 뒤 한자리씩 소수로만 변경하면서 돌리면 어떨까??

- 4자리의 숫자를 한개씩 바꾸며 재귀방식으로 구현하면 4자리의 수에서 한개를 골라 변경한다. (이 때 변경한 수는 소수) basecase는 첫번째 입력한 수와 두번째 입력이 같을 때

==>> 무한루프에 빠진다. 이유는 첫번째 수가 두번째 수로 가지 못할 확률이 있는데 그 부분에서 basecase처리를 못해서 계속 재귀에 빠지게 된다.

 

bfs방식으로 해서 queue가 다 돌았는데 첫번째 수가 두번째 수로 가지못할 때 Impossible을 출력해주는 방향으로 가면 위의 재귀처럼 무한루프에 빠지지 않을 것 같다.

 

 

 

• 코드

 

 

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static boolean[] primes;
	static Queue<int[]> queue;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		sb = new StringBuilder();

		int testcase = in.nextInt();
		primes = new boolean[10000];
		
		for (int i = 0; i < testcase; i++) {
			Arrays.fill(primes, false);
			bfs(in.nextInt(), in.nextInt());
		}
	}

	private static void bfs(int preNumber, int postNumber) {
		queue = new LinkedList<>();
		queue.add(new int[] { preNumber, 0 });
		if (preNumber == postNumber) {
			sb.append(0).append("\n");
			return;
		}
		while (!queue.isEmpty()) {
			int[] primeRoot = queue.poll();
			if (!primes[primeRoot[0]]) {
				// 지나온건 다시 안돌아가도록
				primes[primeRoot[0]] = true;
				
				char[] numbers = Integer.toString(primeRoot[0]).toCharArray();

				for (int i = 0; i <= 9; i++) {
					for (int j = 0; j < 4; j++) {
						if (j == 0 && i == 0)   continue;
						
						char temp = numbers[j];
						numbers[j] = (char) (i + '0');
						int changedPrimeNumber = Integer.parseInt(String.valueOf(numbers));
						numbers[j] = temp;
						if (primes[changedPrimeNumber])		continue;
						if (check(changedPrimeNumber)) {
							if (changedPrimeNumber == postNumber) {
								sb.append(primeRoot[1] + 1).append("\n");
								return;
							}
							queue.add(new int[] { changedPrimeNumber, primeRoot[1] + 1 });
						}
					}
				}
			}
		}
		sb.append("Impossible").append("\n");
	}

	private static boolean check(int number) {
		for (int i = 2; i <= (int) Math.sqrt(number); i++) {
			if (number % i == 0)
				return false;
		}
		return true;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

 

 

• 더 빠른 다른 사람 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static boolean[] primeTable = new boolean[10000];
	private static int[] bfsTable = new int[10000];
	private static final int MAX = 10000;
	private static final String IMPOSSIBLE = "Impossible";
	
	private static int T;
	private static StringBuffer answer;
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		answer = new StringBuffer();
		findPrime();
		
		T = Integer.parseInt(in.readLine());
		
		for (int tc = 1 ; tc <= T ; tc++) {
			st = new StringTokenizer(in.readLine());
			int startPrime = Integer.parseInt(st.nextToken());
			int endPrime = Integer.parseInt(st.nextToken());
			initBfsTable();
			int a = findAnswer(startPrime, endPrime);
			if (a < 0) {
				answer.append(IMPOSSIBLE);
			}
			else {
				answer.append(a);
			}
			answer.append("\n");
		}
		System.out.println(answer.toString());
	}
	private static void findPrime() {
		primeTable[0] = false;
		primeTable[1] = false;
		for (int i = 2 ; i <= 9999 ; i++) {
			primeTable[i] = true;
		}
		
		for (int i = 2 ; i <= 9999 ; i++) {
			if (primeTable[i] == true) {
				for (int j = i * 2 ; j <= 9999 ; j += i) {
					primeTable[j] = false;
				}
			}
		}
	}
	
	private static void initBfsTable() {
		for (int i = 1000 ; i <= 9999 ; i++) {
			bfsTable[i] = (primeTable[i]) ? MAX : -1;
		}
	}
	
	private static int findAnswer(int startPrime, int endPrime) {
		int step = 0;
		boolean findflag = false;
		int currP = startPrime;
		
		int[] stack1 = new int[9000];
		int sp1 = 0;
		int[] stack2 = new int[9000];
		int sp2 = 0;
		
		int[] currStack = stack1;
		int currsp = sp1;
		int[] nextStack = stack2;
		int nextsp = sp2;
		
		currStack[currsp++] = startPrime;
		bfsTable[startPrime] = 0;
		
		if (startPrime == endPrime) {
			return 0;
		}
		
		do {
			step++;
			int seed;
			int nextP;
			findflag = false;
			for (int s = 0 ; s < currsp ; s++) {
				currP = currStack[s];
				// 1000 pos
				seed = currP % 1000;
				for (int i = 1 ; i <= 9 ; i++) {
					nextP = i * 1000 + seed;
					if (bfsTable[nextP] > step) {
						bfsTable[nextP] = step;
						findflag = true;
						nextStack[nextsp++] = nextP;
					}
				}

				// 100 pos
				seed = (currP / 1000) * 1000 + currP % 100;
				for (int i = 0 ; i <= 9 ; i++) {
					nextP = i * 100 + seed;
					if (bfsTable[nextP] > step) {
						bfsTable[nextP] = step;
						findflag = true;
						nextStack[nextsp++] = nextP;
					}
				}

				// 10 pos
				seed = (currP / 100) * 100 + currP % 10;
				for (int i = 0 ; i <= 9 ; i++) {
					nextP = i * 10 + seed;
					if (bfsTable[nextP] > step) {
						bfsTable[nextP] = step;
						findflag = true;
						nextStack[nextsp++] = nextP;
					}
				}

				// 1 pos
				seed = (currP / 10) * 10;
				for (int i = 0 ; i <= 9 ; i++) {
					nextP = i + seed;
					if (bfsTable[nextP] > step) {
						bfsTable[nextP] = step;
						findflag = true;
						nextStack[nextsp++] = nextP;
					}
				}
			}
			
			// exchange stack;
			int[] tempStack = currStack;
			currStack = nextStack;
			nextStack = tempStack;
			currsp = nextsp;
			nextsp = 0;
			
		} while(findflag && bfsTable[endPrime] == MAX);
		
		if (!findflag) {
			return -1;
		}
		
		return step;
	}
}