[DFS] 재귀와 스택으로 가볍게 문제 풀기

 

들어가며

저번 포스팅에서는 이전 상태를 기억해야하는 문제가 대표적인 스택 활용법이라고 소개했습니다.(이전 포스팅) 스택과 재귀는 이러한 점에서 비슷한 점이 많습니다. 깊게 파고들어갔다가 다시 나오는 형태는 동일하죠. 오늘은 이러한 유형의 문제를 접했을 때, 재귀를 선택해야 하는지 스택을 선택해야하는지 알아봅시다.

기준	스택 기반 DSF	재귀 DFS
코드 복잡도	스택 선언, 쌍(pair) 관리, 반복문 사용	함수 호출로 구조 단순
가독성	흐름을 따라가기 어려움	논리적으로 단계적이며 자연스러움
성능	비슷함 (N이 작음, 최대 8자리)	거의 차이 없음
정렬	후처리 필요 (벡터 + 정렬)	탐색 순서 조절 가능 (for문 오름차순으로)

저도 디버깅의 난해함과 직관적이지 않은 코드 흐름 때문에 재귀를 외면하곤 했습니다. 하지만 대부분의 DFS 문제는 재귀를 사용하는 것이 편하다고 합니다. 다만 재귀의 깊이가 1만 노드 이상으로 깊어졌을 때는 함수 스택 오버플로가 나올 수 있으므로 스택을 사용해야합니다. 또한 이전 상태의 구조와 저장 방식이 단순하지 않은 경우에는 데이터를 따로 만들어서 스택을 활용할 수 있습니다. 다만 알고리즘 코딩테스트의 경우 이런 경우는 거의 없기 때문에 재귀를 사용하는 것이 편하며, 실무관점에서는 요구사항이 복잡하기 때문에 스택을 활용하는 것이 좋을 것 같습니다.

 

문제

백준 2023: 신기한 소수

자리수를 줄여가면서 얻은 숫자가 모두 소수인 수를 찾는 문제입니다. N의 최대값이 8이라서 작다고 느낄수 있지만 천만 단위입니다. 문제 접근 방식은 가장 큰 자리수부터 소수인지 확인하고 그 다음 자리수를 탐색해나가야합니다. 이전 자릿수가 소수인지를 기억해야하기 때문에 DFS 방식으로 풀겠습니다.

 

풀이

풀이는 두 가지 방법으로 풀어봤습니다. 첫 번째는 스택, 두번째는 재귀입니다.

풀이1(스택)

풀이 과정

• 소수인지 판별하는 함수 작성(이건 패턴화 되어 있기 때문에 여기서 다루지 않겠습니다, 저는 제곱근을 활용한 방식 채택)
• 가장 큰 자리 수 먼저 스택에 넣기(2, 3, 5, 7)(한자리수 소수)
• 하나씩 빼서 다음 수(next)가 소수이면, 다시 스택에 넣기(5인 경우 다음수는 51, 53, 55... -> 짝수는 소수가 아님)
• 자리수가 입력받은 자리수와 같으면 result 리스트에 넣기
• 스택이 모두 비어있을 때까지 위 내용 반복
• result 리스트 정렬 및 출력

// c++ 17
#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;


bool isPrime(int n)
{
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i <= sqrt(n); i++) {
        if ((n%i) == 0) {
            return false;
        }
    }

    return true;
}

int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N;
    cin >> N;

    stack<int> s;
    vector<int> inputs{ 2, 3, 5, 7 };
    for (const auto i : inputs)
        s.push(i);

    vector<int> result;
    while (!s.empty())
    {
        const auto target = s.top();
        s.pop();

        if (to_string(target).size() == N)
        {
            result.push_back(target);
            continue;
        }

        for (int i = 1; i <= 9; i += 2)
        {
            const int num = target * 10 + i;
            if (isPrime(num))
                s.push(num);
        }
    }

    sort(result.begin(), result.end());
    for (const auto& r : result)
        printf("%d\n", r);
}

2,3,5,7 순서대로 스택에 넣었기 때문에 7393이 가장 먼저 스택에 들어갑니다. 자세히 들여다 보겠습니다. 가장먼저 7이 나오고, 71은 소수가 아님, 다음 73은 소수이기 때문에 73 스택 삽입합니다. 다시 73 꺼내서 그 다음 자리수 비교하면 733, 739가 차례로 스택에 삽입됩니다. 다시 739를 꺼내고 마지막 자리수를 비교하면 7393이 타겟이 되어 result에 들어갑니다.

 

풀이2(DFS)

풀이 과정

• num과 digit을 인자로 받는 DFS 함수를 만드는 것이 키포인트
• 재귀함수는 항상 빠져나갈 구멍 먼저 만듭시다.
• 자리수(digit) 조건이 만족하고, 소수이면 출력 후 함수 종료
• next가 소수이면 재귀호출(digit이 늘어났기 때문에 digit+1로 호출)
• main에서는 첫번째 자리수 타겟(2,3,5,7) 만큼 DSF함수 호출

// C++ 17
#include <iostream>
#include <vector>
using namespace std;
int N;

bool isPrime(int num) {
     if (n <= 1) 
        return false;

    for (int i = 2; i <= sqrt(n); i++) {
        if ((n%i) == 0) 
            return false;
    }

    return true;
}

void DFS(int num, int digit)
{
    if (digit == N)
    {
        if (isPrime(num))
        {
            cout << num << endl;
            return;
        }
    }

    for (int i = 1; i < 10; i += 2)
    {
        int next = num * 10 + i;
        if (isPrime(next))
            DFS(next, digit + 1);
    }
}

int main()
{
    cin >> N;
    DFS(2, 1);
    DFS(3, 1);
    DFS(5, 1);
    DFS(7, 1);
}

DFS로 푼 코드가 훨씬 간결합니다.

 

정리

오늘 문제는 전형적인 재귀 DSF 맞춤이었습니다. 하지만 저는 처음부터 스택을 쓰려고 고집했습니다. 스택이든 재귀든 잘 풀면 되지만 더 자연스러운 방법을 채택하는 것이 생산성에 도움이 됩니다. 문제를 처음 접했을 때 자연스럽고 간결하게 풀 수 있는 방법을 찾으려고 꾸준히 노력해봅시다.