[1017번] 소수 쌍

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭 :: http://www.crocus.co.kr/499

2. 에라토스테네스의 체 :: http://www.crocus.co.kr/593

우선 값의 범위가 1000이지만, a와 b를 더했을 때 2000이 될 수 있으므로 에라토스테네스의 체를 이용하여 소수를 2000까지 구해준다.(에라토스테네스의 체는 비트연산으로 구하던, 다른 방식으로 구하던 코드와는 무관하게 구현하면 된다.)

이제 이분매칭으로는 어떻게 접근하냐가 문제이다.

이 문제는 이분매칭으로 접근하기 위해서 홀수와 짝수를 각각 다른 집합으로 나눈다고 생각하면 된다.

문제에서 처음 입력되는 값과 조건에 맞는 이분 매칭된 값을 출력해달라 하였으니

첫 값이 홀수인지, 짝수인지 판별해야한다.

홀수라면 홀수 값들을 이분 매칭에서의 왼쪽으로 두고, 짝수라면 짝수 값들을 이분 매칭에서의 왼쪽으로 둔다.

(이분 매칭 코드에 따라 다르게 해도된다. 필자의 코드는 왼쪽을 기준으로 이분매칭을 하기에 그렇게 하였다.)

두번째로 홀수 개수와 짝수 개수가 맞지 않다면 당연히 이분 매칭이 불가능하니 -1을 출력한다.

세번째로 첫번째 수와 어느 선에 대해서 합이 소수인 이분매칭이 되는지 찾아야하기에 

첫번째 수와는 하나의 선만 연결되어 있도록 설정해준다.

그 방식을 다음과 같은 알고리즘을 이용하였다.

1) 첫 정점과 연결된 간선을 벡터에 담아두고 모두 지운다.

2) 순차적으로 간선을 하나씩 연결해준다.(이분매칭 함수 콜하기 전 하나씩만)

3) 그 간선을 통해 합이 소수인 이분 매칭이 되는지 확인한다(정답을 ans 벡터에 담아준다).

마지막으로 ans를 오름차순으로 정렬(출력 요구사항)을 해주고 출력을 한다.

말로 표현하면 상당히 쉬운 문제같으나, 막상 코딩을 하면 까다로운 문제인 것 같다.

문제를 해결하지 못하였다면 '맞았습니다'에 너무 신경을 쓰지말고 많은 고민을 해보고 이 문제를 풀어보자.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
#include <cmath>
#include <algorithm>
 
#define MAX_N 1001
#define MAX_SOSU 2002
 
using namespace std;
 
bool adj[MAX_N][MAX_N];
vector<int> aMatch, bMatch;
vector<bool> visit;
vector<int> ans;
 
// 에라토스테네스 체
unsigned char sieve[(MAX_SOSU + 7) / 8];
 
inline bool isPrime(int k)
{
    return sieve[k >> 3] & (1 << (k & 7));
}
 
inline void setComposite(int k)
{
    sieve[k >> 3] &= ~(1 << (k & 7));
}
 
void eratosthenes(int n)
{
    memset(sieve, 255, sizeof(sieve));
    setComposite(0);
    setComposite(1);
 
    int sqrtn = int(sqrt(n));
    for (int i = 2; i <= sqrtn; ++i)
        if (isPrime(i))
            for (int j = i*i; j <= n; j += i)
                setComposite(j);
}
 
 
bool dfs(int a)
{
    if (visit[a])
        return false;
 
    visit[a] = true;
 
    for (int b = 0; b < MAX_N; b++)
    {
        if (adj[a][b])
        {
            // 두 노드의 합이 소수여야 매칭을 할 수 있다.
            if (isPrime(a + b) && (bMatch[b] == -1 || dfs(bMatch[b])))
            {
                aMatch[a] = b;
                bMatch[b] = a;
 
                return true;
            }
        }
    }
 
    return false;
}
 
int bipartiteMatch()
{
    aMatch = vector<int>(MAX_N, -1);
    bMatch = vector<int>(MAX_N, -1);
 
    int size = 0;
 
    for (int start = 0; start < MAX_N; start++)
    {
        visit = vector<bool>(MAX_N, false);
 
        if (dfs(start))
            size++;
    }
 
    return size;
}
 
int main()
{
    eratosthenes(MAX_SOSU); // 2002번째까지 소수 찾기
 
    int n;
 
    vector<int> even;
    vector<int> odd;
 
    scanf("%d", &n);
 
    // 이분 매칭위해 분할
    int firstNum = -1; // 첫번째 수
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        // 첫번째 수 찾아내기
        if (firstNum == -1)
            firstNum = val;
 
        if (val % 2 == 1)
            odd.push_back(val);
 
        else
            even.push_back(val);
    }
 
    // 짝이 안맞으면 -1
    if (odd.size() != even.size())
    {
        printf("-1");
        return 0;
    }
 
 
    // 홀수번호가 첫번호면 홀수 번호를 왼쪽으로 해서 모두 연결
    if (firstNum % 2 == 1)
    {
        for (int i = 0; i < odd.size(); i++)
            for (int j = 0; j < even.size(); j++)
                adj[odd[i]][even[j]] = 1;
    }
 
    // 짝수번호가 첫번호면 짝수 번호를 왼쪽으로 해서 모두 연결
    else
    {
        for (int i = 0; i < even.size(); i++)
            for (int j = 0; j < odd.size(); j++)
                adj[even[i]][odd[j]] = 1;
    }
 
    vector<int> firstLine;
    // 첫 정점과 연결된 간선 모두 찾고 지워주기
    for (int i = 0; i < MAX_N; i++)
    {
        if (adj[firstNum][i] == 1)
        {
            firstLine.push_back(i);
            adj[firstNum][i] = 0;
        }
    }
 
    // 하나씩 선 연결해주면서 돌리기
    int pos = 0;
    bool go = false;
    for (int i = 0; i < MAX_N; i++)
    {
        if (go == false && pos < firstLine.size())
        {
            adj[firstNum][firstLine[pos]] = 1;
            pos++;
 
            go = true;
        }
 
        if (go == true && adj[firstNum][i] == 1)
        {
            int get = bipartiteMatch();
 
            if (get == odd.size())
                ans.push_back(i);
 
            adj[firstNum][i] = 0;
 
            go = false;
        }
    }
 
    sort(ans.begin(), ans.end());
 
    if (ans.size() == 0)
        printf("-1");
 
    else
        for (int i = 0; i < ans.size(); i++)
            printf("%d ", ans[i]);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>