BOJ) 1017. 소수 쌍

문제:

지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다.

1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23

또는

1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23

수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 1 + 12 = 13으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 예제의 답은 4, 10이다.

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

해설:

수들을 합쳐 짝을 지으기 위해서는 이분 매칭의 개념을 사용해야 한다.

입력 리스트들을 왼쪽 set에 넣고, 똑같은 입력 리스트를 오른쪽 set에 넣고

서로 더하면 소수가 되는 수들을 edge로 짝짓는다. (단, 똑같은 숫자는 비교 x)

그 후에는, 왼쪽 set의 맨 첫 번째 숫자와  오른쪽 set에 있는 숫자 중 하나를 고정시켜가며 (이 숫자는 epoch마다 바꾼다) Maximum Matching이 N개가 되는 지 확인한다.

(리스트의 모든 숫자들을 왼쪽과 오른쪽 둘 다 넣기 때문에 Maximum Matching의 size가 N이 됨.)

코드:

#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N;
bool adj[55][55];
int aMatched[55], bMatched[55];
bool visited[55];
bool sosu[2005];

bool dfs(int p){
        if(visited[p]) return 0;
        visited[p] = 1;
        for(int i=0; i<N; i++){
                if(adj[p][i]){
                        if( bMatched[i] == -1 || dfs(bMatched[i])){
                                bMatched[i] = p;
                                aMatched[p] = i;
                                return 1;
                        }
                }
        }
        return 0;
}

int main(){
        cin>>N;
        vector<int> ans;
        sosu[0] = 1; sosu[1] = 1;
        for(int i=2; i<=2000; i++){
                if( sosu[i] == 0){
                        for(int j=2*i; j<=2000; j+=i){
                                sosu[j] = 1;
                        }
                }
        }
        int arr[51];
        for(int i=0; i<N; i++)  scanf("%d",&arr[i]);
        for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                        if( sosu[arr[i]+arr[j]] == 0){
                                adj[i][j] = 1;
                        }
                }
                adj[i][i] = 0;
        }

        for(int i=0; i<N; i++){
                if(adj[0][i]){
                        int size = 2;
                        memset(bMatched,-1,sizeof(bMatched));
                        for(int j=1; j<N; j++){
                                memset(visited,0,sizeof(visited));
                                aMatched[0] = i; aMatched[i] = 0;
                                visited[0] = 1; visited[i] = 1;
                                bMatched[i] = 0; bMatched[0] = i;
                                size += dfs(j);
                        }
                        if(size == N) ans.push_back(arr[i]);
                }
        }
        sort(ans.begin(),ans.end());
        for(int i=0; i<ans.size(); i++) cout<<ans[i]<<" ";
        if(ans.size() == 0) cout<<"-1";
}