[JAVA] 백준 2023 깊이 우선 탐색(DFS)

 

 

 

2023번: 신기한 소수

문제

수의 자리 N이 주어졌을 때, 1의 자리, 10의 자리, … , 10^(N-1)자리 수가 모두 소수인 값을 오름차순 정렬로 출력하시오.

풀이

해당 문제는 DFS 뿐만 아니라 소수의 특징도 알고 있다면 빠르게 풀 수 있다.

소수의 특징

1. 1의 자리 소수는 반드시 2, 3, 5, 7 만 올 수 있다.
2. 2 이상의 자리 소수는 반드시 1, 3, 7, 9 만 올 수 있다.

이 두 특징으로 인해 DFS가 훨씬 빠르게 진행할 수 있다.

두 가지 경우를 나눠서 DFS를 진행한다.

static int[] start = {2, 3, 5, 7};
static int[] value = {1, 3, 7, 9};

탐색

1자리씩 탐색하면서 수를 추가하고 소수를 판별한다.

DFS

public static DFS(int num, int j){
    // 만약 자릿수가 같다면 출력 (소수 판별은 DFS 재귀 이전에 한다.)
    if(j == N){
        sb.append(num).append("\n");
    }
    // 숫자의 자릿수를 높인다.
    num *= 10;

    // 자릿수가 만약 첫 번째라면 start 배열로 탐색한다.
    if(j == 0){
        for(int x : start){
            if(isPrime(num + x)) DFS(num+x, j+1);
        }
    }
    // 자릿수가 만약 두 번째 자리 이상이라면 value 배열로 탐색한다.
    else{
        for(int x : value){
            if(isPrime(num + x)) DFS(num+x, j+1);
        }
    }
}

소수 판별

public static boolean isPrime(int num){
    // 숫자의 제곱근까지 나눠준다.
    for(int i=2; i<Math.sqrt(num); i++){
        // 나누어 떨어지면 소수가 아님.
        if(num % i == 0) return false;
    }
    // 나누어 떨어지는 것이 없다면 소수
    return true;
}

전체 코드

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

class Main {
    static int[] starter = {2,3 , 5, 7};
    static int[] value = {1, 3, 7, 9};
    static int N;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        DFS(0, 0);
        System.out.println(sb);
    }
    public static void DFS(int num, int j){
        if(j == N){
            sb.append(num).append("\n");
        }

        num *= 10;
        if(j == 0){
            for(int x : starter){
                if(isPrime(num + x))
                     DFS(num + x, j+1);   
            }
        }else{
            for(int x: value){
                if(isPrime(num + x))
                    DFS(num + x, j+1);
            }
        }


    }
    public static boolean isPrime(int num){
        for(int i=2; i<Math.sqrt(num); i++){
            if(num % i == 0) return false;
        }
        return true;
    }     
}

해결