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

문제 정리

• 두 네자리 소수 N, M
• N을 M으로 바꾸는 최소 변환 횟수?
• 한번에 N에서 한자리만 바꿀 수 있고 바꾼 숫자도 소수여야함

문제 해결 방법

• BFS로 풀 수 있다.

  1. 시작 : N
  2. 도착 : M
  3. 정점 : 수
  4. 간선 : 수 -> 수
  5. 가중치 : 변하는 수 = 1

• 두 네자리 소수이므로 정점의 개수는 10000보다 작다.

  정확하게는 네자리 소수의 개수보다 작다.

  그래서 정점이 그렇게 크지 않아 시간 안에 구할 수 있다.

• 즉, BFS + 소수 판별

코드

• click

코드 설명

• 에라토스테네스의 체

  // Sieve of Eratosthenes
  for (int i = 2; i < 10001; i++) {
    if (prime[i] == false) {
      for (int j = i * i; j < 10001; j += i) {
        prime[j] = true;
      }
    }
  }
  

  "에라토스테네스의 체는 소수를 구할 때 자주 사용한다. 알아 두는게 좋다."

• int[] d = new int[10001]; //Record dist

  BFS를 사용할 때 각 소수까지 갈 수 있는 거리를 구하는 배열

• boolean[] c = new boolean[10001]; //Check visit

  BFS를 사용할 때 방문했는지 확인하는 배열

  이 배열이 필요한 이유는

  index(천의 자리부터 일의 자리까지)도 0부터 3까지 다 찾고, digit(교환하는 수)도 0부터 9까지 다 찾는데

  즉, 모든 수를 다 찾으므로 이미 방문한 소수를 다시 방문할 수 있다.

  다시 방문하게 되면 d배열의 값이 아예 달라질 수 있기 때문이다.

• change함수

      static int change(int num, int index, int digit) {
          if (index == 0 && digit == 0) {
              return -1;
          }
          //String s = Integer.toString(num);
          String s = String.valueOf(num);
          StringBuilder sb = new StringBuilder(s);
          sb.setCharAt(index, (char)(digit + '0'));
          return Integer.parseInt(sb.toString());
      }
  

  num의 index 자리를 digit로 바꾼다.

  • 먼저 그 수를 문자로 바꾸고
  • 문자의 index번째를 digit으로 바꾸고
  • 다시 문자열을 정수로 바꿔서 리턴

  💡 String은 내부의 문자열을 수정할 수 없다.

  java.lang 패키지의 StringBuffer 또는 StringBuilder 클래스를 사용하는 것이 좋다.