백준 1963 (소수 경로) - java

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

1963번: 소수 경로

BFS 유형의 문제이다. 4자리수에서 바꾼 비밀번호도 4자리수이다. 고로 board 배열을 10000 크기로 진행하여 해당 수에 대한 방문 여부를 계속 확인해주면 되는 문제이다.

 

4자리에 대해 각 자리의 숫자를 바꿔가며 변화된 수가 소수인지 판단하고 체크해가면 되는 문제이다.

 

import java.io.*;
import java.util.*;
public class Main {
    static String start;
    static String target;
    static int[] visit;
    static char[] change = {'0','1','2','3','4','5','6','7','8','9'}; // 각 자리를 해당 숫자로 변경
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());

        for(int i=1;i<=count;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            visit = new int[10001]; // 1000 - 9999 까지가 숫자의 범위
            start = st.nextToken();
            target = st.nextToken();

            if (start.equals(target)) {
                System.out.println(0); // 시작점과 끝점이 동일한 경우는 0번
            } else {
                int result = bfs();
                if (result == -1)
                    System.out.println("Impossible");
                else {
                    System.out.println(result);
                }
            }
        }
        br.close();
    }
    static int bfs()
    {
        Queue<String> q = new LinkedList<>();
        q.add(start);
        visit[Integer.parseInt(start)] = 1; // 시작 처리

        while(!q.isEmpty())
        {
            String cur = q.poll();
            if(cur.equals(target)) // 문제는 결국 최솟값을 찾는 것이기 때문에 이와 같은 처리가 필요하다
            {
                if(visit[Integer.parseInt(target)]==0)
                {
                    visit[Integer.parseInt(target)] = visit[Integer.parseInt(cur)];
                }  // 목적지 숫자에 처음 방문하는 경우

                else if(visit[Integer.parseInt(target)]>visit[Integer.parseInt(cur)])
                {
                    visit[Integer.parseInt(target)] = visit[Integer.parseInt(cur)];
                } // 목적지 숫자에 도달한 적이 있지만 더 작은 횟수로 도달한 경우
            }
            for(int i=0;i<4;i++) // 4자리 수 (1000의 자리부터 접근)
            {
                char[] carr = cur.toCharArray(); // 자리의 숫자를 변경하기 위해 char 형 배열로 변환
                for(int j=0;j<=9;j++) // 0-9까지 숫자를 바꿔본다
                {
                    if(i==0&&j==0) // 맨 앞 즉 1000의 자리는 0이 될 수 없다 !
                        continue;

                    carr[i] = change[j]; // 해당 자리의 숫자를 변경
                    String tmp = new String(carr);
                    
                    //해당 숫자에 처음 방문하거나 방문한 적이 있지만 더 적은 횟수로 재도달한 경우
                    if(visit[Integer.parseInt(tmp)]==0||visit[Integer.parseInt(tmp)]>visit[Integer.parseInt(cur)]+1)
                    {    
                        // 소수 판단
                        if(isPrime(Integer.parseInt(tmp)))
                        {
                            // 갱신
                            visit[Integer.parseInt(tmp)]=visit[Integer.parseInt(cur)]+1;
                            q.add(tmp);
                        }
                    }
                }
            }
        }
        return visit[Integer.parseInt(target)]-1;
    }
    
    // 소수 판단 알고리즘
    static boolean isPrime(int num)
    {
        // 2부터 해당 숫자의 제곱근까지만 점검해도 소수 판단 가능
        for(int i=2;i<=(int)Math.sqrt(num);i++)
        {
            if(num%i==0)
                return false;
        }
        return true;
    }
}