def sieve():
prime = set(); check = [0]*2000
for n in range(2,2000):
if check[n]:
continue
prime.add(n)
for n in range(n,2000,n):
check[n] = 1
return prime
def DFS(i):
if visited[i]:
return
visited[i] = 1
for e in graph[i]:
if not match[e]:
match[e] = i
return 1
for e in graph[i]:
if DFS(match[e]):
match[e] = i
return 1
def solve():
global visited
for i in range(2,N):
visited = [0]*N; visited[1] = 1
if not DFS(i):
return
return 1
input()
nums = [*map(int,input().split())]
even = [0]; odd = [0]
for n in nums:
if n%2:
even.append(n)
else:
odd.append(n)
if nums[0]%2:
even,odd = odd,even
N = len(odd); result = []
if N==len(even):
graph = [[] for i in range(N)]
prime = sieve()
for i in range(1,N):
for j in range(1,N):
if odd[i]+even[j] in prime:
graph[i].append(j)
for r in graph[1]:
match = [0]*N; match[r] = 1
if solve():
result.append(even[r])
print(*sorted(result) if result else [-1])이분매칭 응용문제
서로 다른 두 수의 합으로 소수를 만들려면 반드시 두 수 중 하나는 짝수 하나는 홀수여야함을 이용하는 문제이다.
풀이를 설명하면,
1. 에라토스테네스의 체 방식으로 1~2000 사이의 소수를 모두 구한다.
2. 짝수는 짝수끼리, 홀수는 홀수끼리 모은다. 이때 짝수와 홀수의 개수가 다르면 -1을 출력
3. 첫번째 숫자가 짝수인지 홀수인지에 따라 기준집단으로 잡고, 짝수-홀수 사이에 더했을 때 소수가 되는 경우에 그래프로 연결한다.
4. 첫번째 숫자를 연결하고 나서, 이분매칭 알고리즘으로 모든 숫자를 매칭할 수 있는지 판별하고 가능한 경우 저장한다.
5. 4에서 저장한 숫자를 오름차순으로 출력한다.
이분매칭이라는 사실을 적절하게 숨긴 재미있는 문제였다.
오늘의 교훈) 다양한 이분매칭 활용문제를 해결해보자