[JAVA] 백준 1963 : 소수 경로

문제

1963번: 소수 경로

해결방법

문제를 읽어보면 가능한 비밀번호는 1000 ~ 9999 사이의 숫자이다.

그렇기 때문에 에라토스테네스의 채를 이용해서 9999까지의 소수를 찾아내고

현재 비밀번호에서 각 자리수를 하나씩 변경하며 그 수가 소수라면 다음으로 또 한자리는 변경하는 방식으로

목표 비밀번호까지 최소한의 횟수를 찾는 문제이다.

 

순서를 정리하면

1. 9999까지 소수를 찾는다.

2. 각 자리수를 변경하며 목표 비밀번호를 찾는데, 거쳐가는 비밀번호도 모두 소수인지 확인해야한다.

추가적으로 1000 아래의 숫자는 해당이 안되기때문에 (0010, 0234 같은 경우) 천의 자리 수는 1부터 9까지만 변경해야한다.

 

DFS를 사용하게되면 최소 횟수를 찾기위해 모든 경우의 수를 다 보아야하므로 시간초과가 나서 BFS를 사용해야한다.

필자는 Nums 클래스를 이용해 cnt가 작은 숫자들부터 탐색하도록하는 우선순위큐를 사용했다.

 

자릿수를 분리하는 방법은 생각나는대로 작성해서 아마 효율적이진 않은 것 같다.

다른 더 좋은 방법이 있을 것 같다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_G4_1963 {
	static boolean[] isPrime = new boolean[10000];
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		// 9999번까지의 소수를 찾음
		Arrays.fill(isPrime, true);
		isPrime[1] = false;

		for (int i = 2; i < 10000; i++) {
			if (isPrime[i]) {
				for (int j = 2; i * j < 10000; j++)
					isPrime[i * j] = false;
			}
		}

		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			visited = new boolean[10000];

			int result = bfs(start, end);
			if (result == -1)
				sb.append("Impossible\n");
			else
				sb.append(result + "\n");
		}
		System.out.println(sb);
	}

	static int bfs(int start, int end) {
		PriorityQueue<Nums> q = new PriorityQueue<>();
		q.offer(new Nums(start, 0));
		visited[start] = true;

		while (!q.isEmpty()) {
			Nums cur = q.poll();

			if (cur.num == end) return cur.cnt; // 우선순위큐에서는 가장 먼저 도착한 탐색이 최소 횟수

			// 천의 자리수 변경
			int temp = cur.num % 1000;
			for (int i = 1; i < 10; i++) {
				int nNum = i * 1000 + temp;
				if (nNum != cur.num && isPrime[nNum] && !visited[nNum]) {
					q.offer(new Nums(nNum, cur.cnt + 1));
					visited[nNum] = true;
				}
			}

			// 백의 자리수 변경
			int cheun = (cur.num / 1000) * 1000;
			temp = cur.num % 100;

			for (int i = 0; i < 10; i++) {
				int nNum = cheun + (i * 100) + temp;
				if (nNum != cur.num && isPrime[nNum] && !visited[nNum]) {
					q.offer(new Nums(nNum, cur.cnt + 1));
					visited[nNum] = true;
				}
			}

			// 십의 자리수 변경
			int cheunBeck = (cur.num / 100) * 100;
			temp = cur.num % 10;

			for (int i = 0; i < 10; i++) {
				int nNum = cheunBeck + (i * 10) + temp;
				if (nNum != cur.num && isPrime[nNum] && !visited[nNum]) {
					q.offer(new Nums(nNum, cur.cnt + 1));
					visited[nNum] = true;
				}
			}

			// 일의 자리수 변경
			int cheunBeckShip = (cur.num / 10) * 10;

			for (int i = 0; i < 10; i++) {
				int nNum = cheunBeckShip + i;
				if (nNum != cur.num && isPrime[nNum] && !visited[nNum]) {
					q.offer(new Nums(nNum, cur.cnt + 1));
					visited[nNum] = true;
				}
			}
		}
		return -1;
	}

	static class Nums implements Comparable<Nums> {
		int num;
		int cnt;

		Nums(int num, int cnt) {
			this.num = num;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Nums o) {
			// TODO Auto-generated method stub
			return cnt - o.cnt;
		}
	}
}