[C++] DFS 관련 문제 (백준 2023번, 신기한 소수)

[C++] 깊이 우선 탐색 (DFS)

DFS를 활용할 수 있는 문제 중 하나로 백준 온라인 저지의 2023번 "신기한 소수" 문제를 풀이해본다.

---

신기한 소수의 정의와 문제의 입력과 출력이 아래와 같이 정의된다.

Reference: https://www.acmicpc.net/problem/2023

문제 분석 및 해결 전략

숫자의 각 자리를 확장하면서 조건을 만족하는지를 확인해야 하므로, DFS를 활용한 재귀 함수의 사용이 적절하다는 생각을 해볼 수 있다.

 

우선, 한 자리의 소수는 정해져있으므로 2, 3, 5, 7에서 시작하는 것을 생각할 수 있다.

다음으로는 자리수를 확장하는 과정이다. 현재 숫자의 마지막 자리에 1, 3, 5, 7, 9를 순차적으로 추가할 수 있다. 짝수가 마지막 자리에 있으면 2를 인수로 가지므로 소수가 될 수 없다.

그리고 새롭게 형성된 숫자가 소수인지 확인해야 한다. 소수인지 확인하는 방법은 해당 숫자의 제곱근까지의 자연수 중에서 약수가 있는지를 판단하면 된다. (제곱근까지 중에서 나머지가 0인 숫자가 있다면 그것은 약수이므로 확인하는 숫자는 소수가 아님)

만약 소수라면, 자리수를 늘려가며 재귀적으로 위의 과정을 계속하면 된다.

그러다가 숫자의 길이가 N에 도달하면 해당 숫자를 출력한다. 그리고 다음 숫자에 대해 똑같은 과정을 수행하면 된다.

 

이 전략을 코드로 구현하는 방법은 다양하다.

구현

소수를 찾기 위한 isPrime() 함수와 재귀적으로 신기한 소수를 찾는 findAmazingPrimes() 함수를 만들었다.

findAmazingPrimes() 함수의 입력은 달라질 수 있다.

#include <iostream>
#include <vector>
// sqrt (제곱근)을 위함
#include <cmath>

using namespace std;

// 소수 판별 함수
bool isPrime(int num) {
    if (num < 2) return false;
    int sqrtNum = sqrt(num);
    for (int i = 2; i <= sqrtNum; ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

// DFS를 이용한 신기한 소수 탐색
void findAmazingPrimes(int currentNum, int currentLength, int targetLength) {
    if (currentLength == targetLength) {
        cout << currentNum << endl;
        return;
    }
    for (int digit : {1, 3, 5, 7, 9}) {
        int newNum = currentNum * 10 + digit;
        if (isPrime(newNum)) {
            findAmazingPrimes(newNum, currentLength + 1, targetLength);
        }
    }
}

int main() {
    int N;
    cin >> N;
    // 초기 한 자리 소수에서 시작
    for (int prime : {2, 3, 5, 7}) {
        findAmazingPrimes(prime, 1, N);
    }
    return 0;
}

소수 판별 시 제곱근까지만 확인하여 연산량을 줄일 수 있었고, 문제에서 입력이 최대 8자리로 제한되므로, 일반적인 재귀 깊이 제한에 도달하지 않는다. 그러나 재귀 호출이 많아질 경우 스택 오버플로우를 방지하기 위해 주의해야 한다.

---

이 문제는 DFS와 백트래킹을 활용하여 숫자의 각 자리를 확장하며 조건을 만족하는지를 확인하는 전형적인 문제이다. 직접 구현해보며 DFS의 동작 원리 뿐만 아니라 소수 판별 방법까지도 익히는 데 도움이 될 수 있었다.