[BOJ] 1963 소수경로 - JAVA

1. 문제

1963번: 소수 경로

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

---

2. 풀이

InitPrime

static boolean배열에 소수인지 아닌지 판별할 수 있도록 값을 넣었다.

소수이면 false, 소수가 아니라면 true가 저장된다.

static boolean[] prime = new boolean[10000];
private static void initPrime(){
   //소수이면 false
   prime[0] = prime[1] = true;
   for(int i=2;i<10000;i++){
      if(prime[i]) continue;
      for(int j=i*2;j<10000;j+=i){
         prime[j] = true;
      }
   }
}

 

BFS

a,b를 받아서 a가 b에 도달하는 데 얼마나 걸리는 지 확인하는 메서드다. 큐를 사용했다.

queue에 먼저 a를 넣고 queue가 빌 때까지 반복한다.

 

1.  만약 방문한 적 있다면 continue한다.

2.  visited[num] = true로 방문처리한다.

3.  만약 현재 노드가 b와 동일하다면 value를 리턴하고 끝낸다. 여기서 value는 a부터 해당 숫자까지 도달하는 데 걸린 최소횟수다.

4.  numAr에 한자리수씩 숫자를 넣는다. 나중에 거듭제곱할 때 편하게 하기 위해서 0은 일의 자리, 3은 천의 자리로 했다.

5. 자릿수 하나하나 보면서 그 자리에 다른 숫자를 넣고 탐색한다.

5-1.  천의 자리일 때 j가 0일 수 없다. 숫자는 1000이상이기 때문이다. continue한다.

5-2.  원래의 수와 동일하면 안된다. numAr[i]==j이면 continue한다.

5-3.  새로 계산한 숫자가 소수이고 방문한 적 없다면 큐에 넣는다.

 

큐가 비었는데도 return되지 않았다면 -1을 리턴한다.

private static int solve(int a, int b){
   Queue<int[]> queue = new ArrayDeque<>();
   boolean[] visited = new boolean[10000];
   queue.offer(new int[]{a,0});

   int[] now;
   int num;
   int[] numAr = new int[4];
   while(!queue.isEmpty()){
      now = queue.poll();
      num = now[0];
      if(visited[num]) continue;
      visited[num] = true;

      if(num==b){
         //끝나는 조건
         return now[1];
      }

      //숫자 해체
      for(int i=0;i<4;i++) {
         numAr[i] = num%10;
         num/=10;
      }

      for(int i=0;i<4;i++){
         for(int j=0;j<10;j++){
            if(i==3 && j==0) continue;//천의자리는 0이면 안됨
            if(numAr[i]==j) continue;//원래 수와 동일하면 안됨
            int next = (int) (now[0]-(numAr[i]-j)*Math.pow(10,i));
            //소수이고 방문한 적 없어야함
            if(!prime[next] && !visited[next]) queue.offer(new int[]{next,now[1]+1});
         }
      }
   }

   return -1;
}

 

Main

1.  먼저 소수배열을 초기화시킨다.

2.  값을 입력받은 후 solve메서드 실행결과를 result에 저장한다.

3.  만약 result가 -1이라면 불가능한 경우이므로 Impossible을 sb(StringBuilder)에 더한다.

4.  3의 경우가 아니라면 result를 sb에 더한다.

5.  마지막으로 sb를 출력한다.

public static void main(String[] args) throws IOException {
   initPrime();

   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(in.readLine());
   StringTokenizer st;
   StringBuilder sb = new StringBuilder();
   while(T-->0){
      st = new StringTokenizer(in.readLine());
      int result = solve(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
      if(result<0) sb.append("Impossible\n");
      else sb.append(result).append('\n');
   }

   System.out.print(sb);
}

---

3. 결과