[Programmers]완전탐색 > 소수찾기(c++)

https://programmers.co.kr/learn/courses/30/lessons/42839#

코딩테스트 연습 - 소수 찾기

DFS를 이용해서, 모든 경우를 탐색하면서 소수를 찾았다.

처음엔 어떻게풀어야하는지 감이 잡히지 않았는데 구글검색으로 DFS를 써서 풀수 있는걸 알았다.

1.  num안에 numbers로 만들수있는 숫자를 하나씩 뽑아 저장한다. (예시가 17이면 1, 7, 17)

2. DFS안에 numbers[0]이 들어오면, isVisited[0] = true 로 방문표시를 하고, 소수 판별 후 방문하지 않은 수에 대해서 DFS를 반복한다.

3. 소수 판별은 에라토스테네스의 체 방법으로 해결했다.  (소수 판별할때 하나씩 소수인지 찾다가 시간초과가 났음)

4. 소수 판별 후 중복되는 숫자를 없애기 위해서 set에다가 소수 리스트를 저장했다.

 

 

 

 

---

main포함 코드

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstdlib>
#include <set>
#include <math.h>
#define SIZE 10
using namespace std;

bool isVisited[SIZE];
set<int> prime_list;

void check(string num){
    int prime = stoi(num);
    bool prime_flag = true;
    //소수 판별 후 , 소수면 +1
    for(int i=2;i<=sqrt(prime); i++) if( prime % i == 0) {prime_flag = false; break;}
    if(prime == 1 || prime == 0) prime_flag = false;
    if(prime_flag == true) prime_list.insert(prime);
}

void DFS(int x, string numbers, string num){
    num += numbers[x];
    
    if(isVisited[x] == true) return;
    isVisited[x] = true;
    check(num);
    for(int i=0;i<numbers.size();i++)if(isVisited[i] == false)DFS(i, numbers, num);
    isVisited[x] = false;
    
}

int solution(string numbers) {
    string num;
    for(int i=0;i<numbers.size();i++) {DFS(i, numbers, num);}
    return prime_list.size();
}

int main(int argc, const char *argv[])
{
    solution(numbers);
    return 0;
}