[백준][C++]2023번 신기한 소수

문제

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

2023번: 신기한 소수

 

 

풀이

• N자리까지 재귀 함수 형태로 탐색 ⇒ DFS의 형태로 탐색

 

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색) 알고리즘

 

 

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void DFS(int n, int depth);
bool isPrime(int n);
static int N;

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

  cin >> N;

  DFS(2, 1);
  DFS(3, 1);
  DFS(5, 1);
  DFS(7, 1);
  
  return 0;
}

// DFS 구현
void DFS(int n, int depth)
{
  if(depth == N)
  {
    cout << n << "\n";	// 소수이면 수 출력
    return ;	// 탐색 종료
  }

  for(int i = 1; i <= 9; i = i + 2)	// 짝수이면 더는 탐색할 필요가 없음
  {
    int num = n * 10 + i;
    // 소수이면 재귀로 자릿수를 늘림
    if(isPrime(num))
    {
      DFS(num, depth + 1);
    }
  }
}

// 소수 구하기 함수
bool isPrime(int n)
{
  for(int i = 3; i <= sqrt(n); i++)
  {
    if(n % i == 0)
    {
      return false;
    }
  }
  
  return true;
}

 

 

오답

#include <iostream>

using namespace std;

void DFS(int number, int jarisu);
bool isPrime(int num);
static int N;

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

  cin >> N;

  DFS(2, 1);
  DFS(3, 1);
  DFS(5, 1);
  DFS(7, 1);
}

void DFS(int number, int jarisu)
{
  if(jarisu == N)
  {
    if(isPrime(number))
    {
      cout << number << "\n";
    }
    return;
  }
  for(int i = 1; i < 10; i++)
  {
    // 짝수이면 더는 탐색할 필요가 없음
    if(i % 2 == 0)
    {
      continue;
    }
    // 소수이면 재귀로 자릿수를 늘림
    if(isPrime(number * 10 + i))
    {
      DFS(number * 10 + i, jarisu + 1);
    }
  }
}

bool isPrime(int num)
{
  for(int i = 2; i <= num / 2; i++)
  {
    if(num % i == 0)
    {
      return false;
    }
  }
  return true;
}