문제 풀이(4)

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

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


class Node{
	int number;
	int step;

	Node(int number ,int step)
	{
		this.number = number;
		this.step = step;
	}
}

public class Solution {

	static int[] A ;

	static ArrayList<Integer>list = new ArrayList<>();

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

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


		while (T-- > 0) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());

			int start = Integer.parseInt(st.nextToken());

			int target = Integer.parseInt(st.nextToken());

			System.out.println( solution(start, target) );
		}

	}


	public static int solution(int start , int target)
	{

			
		A = new int[10000 + 1];

		for (int i = 2; i < 10000; i++) {
			A[i] = i ;
		}


		for (int i = 2; i < Math.sqrt(10000); i++) {
			
			if (A[i] == 0) {
				continue;
			}

			for (int j = i + i; j < 10000; j = j + i) {
				A[j] = 0;
			}

		}


	
		for (int i = 1000; i < 10000; i++) {
			if (A[i] != 0) {
				list.add(A[i]);
			}
		}



		int result = bfs(start , target);

	
		return result;
	}

	public static int bfs(int start , int target)
	{

		boolean[] visited = new boolean[list.size()];

		Queue<Node>Q = new LinkedList<>();

		Q.offer(new Node(start, 0));

		while (!Q.isEmpty()) {
			
			Node now = Q.poll();

			if (now.number == target) {
				return now.step;
			}

			for (int i = 0; i < list.size(); i++) {
				int next = list.get(i);

				if (!function(now.number , next)) {
					continue;
				}

				if (visited[i]) {
					continue;
				}

				visited[i] = true;

				
				Q.offer(new Node(next,now.step + 1));
			}
		}

		return 0;
	}

	public static boolean function(int n1 , int n2)
	{
		char[] c1 = String.valueOf(n1).toCharArray();

		char[] c2 = String.valueOf(n2).toCharArray();

		int diff = 0;

		for (int i = 0; i < Math.min(c1.length, c2.length); i++) {
			if (c1[i] != c2[i]) {
				diff++;
			}
		}

		return diff == 1;
	}
}

solution 함수: 주어진 start 숫자와 target 숫자 사이의 소수들을 리스트에 저장한 뒤, 시작 숫자부터 목표 숫자까지의 최단 거리를 bfs 함수를 이용하여 구한다. 최단 거리를 반환한다.

bfs 함수: 너비 우선 탐색(BFS)을 통해 시작 숫자에서 목표 숫자까지의 최단 거리를 구하는 함수이다. Queue를 사용하여 탐색하며, 현재 숫자에서 인접한 소수들로 이동하면서 최단 거리를 구한다. 최단 거리를 찾으면 해당 거리를 반환한다.

function 함수: 두 개의 숫자가 서로 한 자리만 다른지 확인하는 함수이다. 두 숫자의 각 자리를 비교하면서 다른 자리의 개수를 세고, 다른 자리가 정확히 하나인지 확인한다.