boj, 백준) 1017. 소수 쌍 ( C / C++ )

1. 문제 링크

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

1017번: 소수 쌍

 

2. 문제 개요

수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다.

남는 수 없이 모두 쌍을 만들었을 때 첫 번째 수와 매칭 되는 수를 오름 차수 순으로 나열하라.

 

3. 문제 힌트

소수인지 아닌지 판별하는것 구현하기.

소수 쌍을 만드는것이므로 합해서 소수가 될 수 있는 것들을 간선으로 연결하고

이분 매칭 하기.

 

4. 문제 풀이

우선 특정 수가 소수인지 아닌지를 구별하기 위해 에라토스테네스의 체를 구현하여 소수인지 판별하는 bool 행렬을 만들었다.  그리고 결괏값을 오름차순으로 나열해야 하므로 첫 번째 숫자를 제외하고 나머지 수들을 오름차순으로 정렬한다.

 정렬하고 나서 모든 수에 대해 더해서 소수가 된다면 간선으로 이어준다. (이분 그래프)

 

이문제의 키포인트는 첫 번째 숫자가 갈 수 있는 즉, 쌍이 되는 노드는 고정하고 나머지 노드들이 남김없이 이분 매칭이 되는지 체크하는 것이다.

따라서 

for(첫 번째 노드의 간선)

 for(모든 노드)

   dfs(이분 매칭)

이런 형식으로 돌아가게 된다.

 

이분 매칭을 할때 보통 누가 특정한 노드와 매칭된다는것은 배제하고 이 이분그래프가 최대 몇개로 매칭이되는지만 따지기 때문에 이분매칭 알고리즘의 흐름을 모르고 그냥 외웠다면 꽤나 고생했을 문제라고 생각한다.

 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int prime_size = 2001, max_size=51;
bool isprime[prime_size];
int n;
vector<vector<int>> adj;
vector<int> value;

bool visited[max_size],s[max_size];
int p[max_size];


void get_prime()
{
	fill(isprime, isprime + prime_size, true);

	isprime[0] = isprime[1] = false;
	int limit = (int)sqrt(prime_size);
	for (int i = 2; i < limit; ++i)
	{
		if (isprime[i] == true) {
			for (int iter = 2; i*iter < prime_size; iter++)
				isprime[i*iter] = false;
		}
	}

	return;
}
bool dfs(int cur)
{
	if (visited[cur] )
		return false;
	visited[cur] = true;

	int len = adj[cur].size();
	for (int i = 0; i < len; ++i)
	{
		int next = adj[cur][i];

		if (p[next] == -1 || dfs(p[next]))
		{
			p[next] = cur;
			s[cur] = true;
			visited[next] = true; //for bidirectional matching

			p[cur] = next;
			s[next] = true;
			return true;
		}
	}
	return false;
}

int main()
{
	get_prime();

	scanf("%d", &n);
	value.resize(n + 1);
	adj.resize(n + 1);

	for (int i = 1; i <= n; ++i)
		scanf("%d", &value[i]);

	//sorting
	sort(value.begin() + 2, value.end());
	
	//make graph
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if(i!=j)
				if (isprime[value[i] + value[j]])
					adj[i].push_back(j);
			
	//bipartite matching
	vector <int> ans;
	int len = adj[1].size();
	for (int iter = 0; iter < len; ++iter)
	{
		int chk = 2;	//because I select one pair.
		fill(p, p + max_size, -1);
		fill(s, s + max_size, false);

		int matched = adj[1][iter];

		for (int i = 1; i <= n; ++i)
		{
			if (s[i])
				continue;
			fill(visited, visited + max_size, false);

			visited[1] = visited[matched] = true;
			p[matched] = 1;
			s[1] = true;
			p[1] = matched;
			s[matched] = true;

			if (dfs(i))
				chk+=2;
		}
		if (chk == n)
			ans.push_back(value[matched]);
	}
	

	len = ans.size();
	if (len == 0)
		printf("-1");
	else
		for (int i = 0; i < len; ++i)
			printf("%d ", ans[i]);

	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~