[BOJ] 2023 신기한 소수

백트래킹은 해를 찾는 도중에 해가 아니면 다시 돌아가서 해를 찾는 알고리즘 기법이다..
dfs로 백트래킹하고 소수판정을 하면 되는 문제다

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

public class Solution2023 {
    static int N;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        sb = new StringBuilder();
        dfs(0, 0);
        System.out.println(sb);
    }

    static void dfs(int num, int depth) {
        if(depth == N) {
            if(isPrime(num)) {
                sb.append(num + "\n");
            }
        }
        for(int i = 1; i <= 9; i++) {
            int n = num * 10 + i;
            if(isPrime(n)) {
                dfs(n, depth+1);
            }
        }
    }

    static boolean isPrime(int num) {
        if(num == 1) return false;

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