[DFS] 백준 2023번

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.
( 1 <= N <= 8 )

 

문제분석

총 4자리라는 가정하에 문제분석 시작
1. 첫번째자리수부터 소수인지 체크하면서 4자리까지 소수 체크가 일어나야한다
2. 해당 구현을 DFS를 이용하여, 한개씩 체크하며 소수인지 체크한다
3. 4자리까지 소수인지 확인이 되면 출력
(뒤의 DFS로 붙이는 값을 1,3,5,7, 9 로 제한 -> 짝수일경우 2로 나누어지므로 어차피 소수가 아님)

• 주의)
  • 소수인지  판독) "에라토스테네스의 체" 이론 이용
    • 에라토스테네스의 경우, 소수인 2,3,5,7를 이용하여 해당 배수를 제거하는 방법을 사용하여 소수를 구하였다
    • 이번 문제에서는, 해당 숫자의 소수를 판독해야하기에 제곱근으로 구하는 방식을 택함 ( 약수를 가지기 위해서는 해당 수의 제곱근 이하의 약수를 가지게 되는 이론을 채택)

 

슈도코드

N(자릿수)
DFS 실행하기 (2,3,5,7로 시작)

DFS 구현{
    if( 자릿수 == size ){
        if(소수) 수 출력하기
        탐색 종료
     }
     
     for( 1,3,5,7,9 배열 반복 ){
         if ( 소수 이면 )
         DFS 실행
      }
}

소수 검증 (숫자){
    if (2 ~ 제곱근까지의 나머지가 0이면 ){
        소수 아님
    }
    if 문에 안걸리면 소수
}

 

 

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class App {
        
    private static int size = 4;
    private static int[] arr = {1,3,5,7,9};
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(bf.readLine()); 
        dfs(2,1);
        dfs(3,1);
        dfs(5,1);
        dfs(7,1);
    }

    private static void dfs(int primeNumber, int count){
        if(count == size){
            System.out.println(primeNumber);
            return;
        }

        for (int j = 0; j < arr.length; j++){
            int next = primeNumber*10 + arr[j];
            if (check(next)){
                dfs(next,count+1);
            }
        }
    
    }

    private static boolean check(int primeNumber){
        for (int i = 2; i <= Math.sqrt(primeNumber); i++) {
            if (primeNumber % i == 0) {
                return false;
            }
        }
        return true;
    }

    
}