UVA524 Prime Ring Problem

DFS, Graph

출처: UVA UVA524 Prime Ring Problem

SOL)
배열의 위치한 연속된 두 원소가 소수가되는 수를 시계방향으로
하나씩 깊이우선탐색으로 고른후 출력.
배열 val을 통하여 원소가 선택된 상태인지 아닌지 판별



[-] Collapse

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;

bool isPrime[50];
bool val[17];
int arr[17];
int n;
void eratosthenes(){
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < 50; i++){
        if (isPrime[i]){
            for (int j = i*i; j < 50; j += i)
                isPrime[j] = false;
        }
    }
}
void DFS(int order){
    if (order == n && isPrime[arr[0] + arr[n-1]]){
        for (int i = 0; i < n-1; i++)
            cout << arr[i] << " ";
        cout << arr[n - 1] << endl;
    }
    else{
        int idx = 2;
        while (1){
            if (isPrime[arr[order - 1] + idx] && val[idx] == false){
                arr[order] = idx;
                val[idx] = true;
                DFS(order + 1);
                val[idx] = false;
            }
            idx++;
            if (idx > n)
                break;
        }
    }
}
int main(){
    //freopen("input.txt", "r", stdin);
    int cases = 1;
    eratosthenes();
    while (cin >> n){
        memset(val, false, sizeof(val));
        for (int i = 0; i < 17; i++) arr[i] = 1;
        if (cases > 1) cout << endl;
        cout << "Case " << cases++ << ":" << endl;
        DFS(1);

    }
}