UVA 514 소수고리(C++)

소수고리는 n개의 원으로 구성되며 각각의 원에는 1부터 n까지의 자연수가 모두 들어가 있으며 인접한 두 원의 합은 항상 소수가 된다.


첫번째 원의 번호는 항상 1이 되어야 한다.

(0<n<=16)n을 입력하면 1부터 시작하는 시계방향과 반시계방향의 숫자들을 출력하는대 다음과 같은 순서로 출력하라.

입력예제)
6
8

출력예제)
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2


dfs를 이용해서 수소고리를 한칸한칸 구해본다.
전칸과 이번칸을 비교해서 두수의 합이 수소 일때 다음칸으로 넘어간다. 그리고 마지막 칸에서 첫번째 칸과의 합이 수소인 것들만 출력한다.


#include <iostream>
#include <windows.h>
#include <math.h>
using namespace std;
int a,ring[16]={1};
bool isPrime[31]={true,true},digit[16];
//따로 초기화 하지 않은bool은 false로 자동 초기화 된다.
void dfs(int num){
     int i;
    
     if(num==a){
                if(isPrime[ring[a-1]]){
                                       for(i=0;i<a;i++){
                                                        cout<<ring[i]<<" ";
               
                                       }
                cout<<endl;
                }
               
                return;
     }
    
     for(i=2;i<=a;i++){
                       if(!digit[i-1]){//false 일때 통과.
                                        
                                     if(isPrime[ring[num-1]+i-1]){
                                                                digit[i-1]=true;
                                                                ring[num]=i;
                                                                dfs(num+1);
                                                                digit[i-1]=false;
                                     }
                       }                                                     
     }
     return;
}
int main(){
   
    int c=0,i,j;
   
    /*dfs에서 일일이 수소판정을 하게되면
    같은 수를 중복으로 수소판정하는 일이발생하고
    루틴수가 어마어마하게 늘어난다*/
    for(i=2;i<31;i+=2){//2의 배수는 수소판정할 필요 없다.
                      isPrime[i]=true;
                      for(j=3;j<=sqrt(i+1);j+=2){
                      /*2의 배수는 소수판정에서 제외되었으므로
                      2의 배수로 나눠봤자 안나눠 떨어진다*/
                                                 if((i+1)%j==0){
                                                                isPrime[i]=false;
                                                                break;
                                                 }
                      }
    }
  
    while(cin>>a){
                  cout<<"Case : "<<++c<<endl;
                  dfs(1);
                 
                  cout<<endl<<endl;
    }
   
    system("PAUSE");
    return 0;
}

실행결과

6 8
Case : 1
1 4 3 2 5 6
1 6 5 2 3 4

Case : 2
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2