[Baekjoon] 1963_소수 경로

Gold IV

문제(출처: https://www.acmicpc.net/problem/1963)

---

< 소수 경로 >

 

문제 풀이 

 

모든 자릿수의 숫자를 바꿔가며 소수인지 확인한다. 소수라면 다음 변환을 계속한다.

 

 my solution (Java)

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

public class _1963_ { // 소수 경로
	static boolean arr[];
	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		arr = new boolean[10000];

		for (int i = 2; i < 5001; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 10000; j += i) {
					arr[j] = true;
				}
			}
		}

		int t = Integer.parseInt(bf.readLine());
		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(bf.readLine());
			String a = st.nextToken();
			String b = st.nextToken();

			result = -1;

			if (a.equals(b)) {
				bw.write("0\n");
			} else {
				search(a, b);

				if(result==-1) {
					bw.write("Impossible\n");
				}else {
					bw.write(result + "\n");
				}
			}
		}
		bw.flush();
	}

	private static void search(String a, String b) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { Integer.parseInt(a), 0 });

		boolean visited[] = new boolean[10000];
		visited[Integer.parseInt(a)] = true;

		while (!queue.isEmpty()) {
			int num[] = queue.poll();

			String temp = Integer.toString(num[0]);
			for (int i = 0; i < b.length(); i++) {
				for (int j = 0; j < 10; j++) {
					if (temp.charAt(i)-'0' == j || (i==0 && j==0)) {
						continue;
					}
					String str = temp.substring(0, i) + j + temp.substring(i + 1, b.length());
					if (arr[Integer.parseInt(str)]) {
						continue;
					}
					if (str.equals(b)) {
						result = num[1] + 1;
						break;
					}
					if (!visited[Integer.parseInt(str)]) {
						visited[Integer.parseInt(str)]=true;
						queue.add(new int[] { Integer.parseInt(str), num[1] + 1 });
					}
				}
			}
			if (result != -1) {
				break;
			}
		}
	}
}

변수)
arr : 소수 판단
t : 테스트 케이스 수
a, b : 네 자리 소수 
result : 두 소수 사이의 변환에 필요한 최소 회수

 

네 자리 수만 소수인지 판단하므로 9999까지 미리 소수를 판단하여 arr에 boolean 값으로 저장한다. 테스트 케이스 수 t를 입력받은 후 t만큼 네 자리 소수 1쌍을 입력받아 a, b에 저장한다. 입력받은 a, b가 같은 값이라면 계산하지 않고 0을 출력한다. 값이 다르다면 search 함수를 호출한다. 만약 변환이 불가능하다면 "Impossible"을 출력하고, 변환이 가능하다면 result 값을 출력한다.

 

search ( String a, String b)

Queue에 [현재 값, 변환 횟수]를 배열로 저장한다. 초기 값인 a를 방문 표시 후 queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) 값을 맨 앞자리부터 하나씩 0~9로 바꾸기

3) 만약 맨 앞자리가 0이거나 바꾸려는 값과 지금 값이 같은 경우는 넘어간다

4) 바꾼 값이 소수가 아니라면 넘어간다

5) 바꾼 값이 b와 일치하다면 result 업데이트 후 종료 

6) 바꾼 값이 소수이고, b와 일치하지 않고, 아직 방문처리 되지 않았다면 방문 처리 후 queue에 추가

---

---