소수 쌍

🤔 접근

주어진 리스트가 소수쌍으로 묶일 수 있는지 확인하는 문제이다. 문제를 풀기 전, 3가지 정도 알고리즘이 필요할 것이라고 생각했다.

1. 이분그래프
   소수쌍으로 묶이는지 확인하기에 앞서 우선 후보들을 추릴 수 있다. 예를 들어 a가 b의 소수쌍이고 b가 c의 소수쌍이라면, a와 c는 절대로 소수쌍이 될 수 없다. 왜냐하면, 2를 제외한 모든 소수는 홀수이고 따라서 홀+짝 또는 짝+홀 로만 소수가 만들어지기 때문이다. 그래서 우선, 홀수집합과 짝수집합으로 구분하여 풀었다.

2. 에라토스테네스의 체
   두 원소 a+b 의 합이 소수인지 판정하는 함수 구현, 소수라면 a -> b 노드 추가

3. 이분 매칭
   소수 판정으로 만든 그래프를 통해 이분탐색을 실시.

처음에는 그닥 어렵지 않을 거라고 생각했는데, 문제를 풀다보면 해결해야 하는 상황이 여럿 발생한다.

내가 겪은 문제상황

1. 첫 번째 원소가 홀수인지 짝수인지 구분
2. 첫 원소와, 첫 원소가 갈 수 있는 다른 집합의 정점들을 하나씩 제거하고 이분탐색을 실행해야함

🖋️ 배운 것

이분탐색 알고리즘을 구현해보며 복습할 수 있었다. (다른 블로그 글 참고하여 작성)
<이분매칭 알고리즘 구현>

#### 이분매칭 알고리즘
# matched_Y : Y 그룹의 노드와 매칭된 X 노드의 번호
# matched_X : X 그룹의 노드와 매칭된 Y 노드의 번호
def dfs(x):
    visited[x] = True
    for y in graph[x]:
        # y 노드와 매칭된 노드가 없는 경우, x 노드와 매칭
        if matched_Y[y] == 0:
            matched_Y[y] = x
            matched_X[x] = y
            return True
        # y 노드가 이미 매칭이 되어있는 경우, y 노드와 매칭되어 있는 노드가 다른 노드와 매칭이 가능한지 확인
        elif not visited[matched_Y[y]] and dfs(matched_Y[y]):
            # 다른 노드와 매칭이 가능한 경우, y 노드와 x 노드를 매칭
            matched_Y[y] = x
            matched_X[x] = y
            return True
    return False

코드

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

#### 이분매칭
def dfs(x, i):
    visited[x] = True
    for y in graph[x]:
        if y == i:
            continue
        if matched_Y[y] == 0:
            matched_Y[y] = x
            matched_X[x] = y
            return True
        # y 노드가 이미 매칭이 되어있는 경우, y 노드와 매칭되어 있는 노드가 다른 노드와 매칭이 가능한지 확인
        elif not visited[matched_Y[y]] and dfs(matched_Y[y], i):
            # 다른 노드와 매칭이 가능한 경우, y 노드와 x 노드를 매칭
            matched_Y[y] = x
            matched_X[x] = y
            return True
    return False

# 소수판별
def is_prime(number):
    if number <= 1:
        return False
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            return False
    return True

n = int(input())
arr = list(map(int, input().split()))

A, B = [], []
# 이분그래프, 인덱스변환
A_idx, B_idx = {}, {}
countA, countB = 1, 1

for i in arr:
    if i % 2 == arr[0] % 2: # 홀수
        A.append(i)
        A_idx[i] = countA
        countA += 1
    else:
        B.append(i)
        B_idx[i] = countB
        countB += 1

graph = [[] for _ in range(len(A)+1)]
for a in A:
    for b in B:
        if is_prime(a+b):
            graph[A_idx[a]].append(B_idx[b])

# tmp에 있는 B 정점들을 하나씩 확인
tmp = graph[1]

# 첫 번째 요소를 그래프에서 제거
graph[1] = []

res = []
for i in tmp: # i 는 B집합 노드들
    matched_X = [0] * (len(A)+1)
    matched_Y = [0] * (len(B)+1)
    cnt = 0
    for j in range(2, len(A)+1):
        if matched_X[j] == 0:
            visited = [False] * (len(A)+1)
            if dfs(j, i):
                cnt += 1

    if cnt == (n // 2 - 1):
        res.append(i)

if not res:
    print(-1)
    exit()
for idx, i in enumerate(res):
    res[idx] = B[i-1]

res.sort()

print(' '.join(map(str, res)))