[BOJ 1017] 소수 쌍

문제

---

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

풀이

---

꽤나 신박한 이분 매칭 응용문제이다.

중복되지 않게 수들이 주어지므로, 홀수와 짝수로 양분할 수 있다.

for문을 돌리며, 첫 번째 숫자와 더해서 소수가 되는 수들에 대해 최대 매칭을 구한다.

물론 첫 번째 숫자와 더해준 수는 미리 매칭 시켜야 한다.

총 매칭 수가 N/2이면, 모든 수를 다 짝지은 것이므로, 출력해 주면 된다.

코드

---

import sys

sieve = [1] * 2001
sieve[0] = 0
sieve[1] = 0

for i in range(2, 2001):
    if sieve[i]:
        for j in range(2, 2000 // i + 1):
            sieve[j * i] = 0


def dfs(cur):
    visit[cur] = 1
    for nxt in graph[cur]:
        if not b[nxt] or (not visit[b[nxt]] and dfs(b[nxt])):
            b[nxt] = cur
            return 1
    return 0


n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
flag = num[0] % 2

graph = [[] for _ in range(n + 1)]

for i in range(1, n + 1):
    if num[i - 1] % 2 == flag:
        for j in range(1, n + 1):
            if (i != j) and sieve[num[i - 1] + num[j - 1]]:
                graph[i].append(j)

ans = []
for i in range(2, n + 1):
    if i in graph[1]:
        b = [0] * (n + 1)
        b[i] = 1

        flow = 1
        for j in range(2, n + 1):
            if j != i:
                visit = [0] * (n + 1)
                visit[1] = visit[i] = 1
                flow += dfs(j)
        
        if flow == n // 2:
            ans.append(num[i - 1])

if ans:
    print(*sorted(ans))
else:
    print(-1)