[백준 알고리즘: python 3] #1017 - 소수 쌍

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

 

1017번 문제는 소수 쌍 문제입니다. 수의 리스트를 입력 받았을 때, 이를 짝지어 만들 수 있는 각 쌍의 합이 모두 소수가 되게 하는 경우, 첫번째 숫자와 짝지어진 숫자를 답으로 출력하는 문제입니다.

 

문제의 예시에는 만약

 

{1, 4, 7, 10, 11, 12} 의 숫자 리스트를 받았다면,

 

1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23

또는

1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23

 

의 경우가 가능합니다. 즉, 각 경우에서 첫번째 숫자(1)와 짝지어진 4, 10이 답이 됩니다.

 

Hint!

이 문제도 역시 DFS로 접근이 가능합니다. 답에서 중요한 점은 모든 쌍들의 합이 소수가 되었을 때, 첫번째 숫자와 짝지어진 숫자가 무엇인가 이기 때문에, 반복문을 시행할 때 첫번째 숫자를 고정시켜 두고 입력받은 리스트의 숫자들을 하나씩 쌍을 이루었을 때 나머지 숫자들로 소수 쌍들을 만들 수 있는가를 확인하는 것이 중요합니다.

 

이 때, DFS는 이분 그래프에서 이분 매칭을 구하기 위해 사용됩니다. 이분 그래프와 이분 매칭에 대한 내용은 "[백준 알고리즘: python 3] #1014 - 컨닝" 글에서 다루고 있으므로 참고해주시길 바랍니다. 이 문제에서 이분 그래프의 두 그룹은 이전 문단에서 언급한 첫번째 숫자와 이번 반복에서 짝지어진 숫자를 제외한 나머지 숫자들의 집합으로 정의가 됩니다. 예를 들어, 입력된 숫자의 리스트가 {1, 4, 7, 10, 11, 12}이라면, 첫번째 숫자인 1과 이번 루프에서 선택된 숫자가 4일 때, 이분 그래프의 두 그룹은 {7, 10, 11, 12}와 이와 동일한 {7, 10, 11, 12}로 이루어 집니다. 이 이분 그래프에서의 이분 매칭을 구했을 때, 매칭이 된 쌍의 개수가 그룹의 숫자의 개수(위의 예시에선 4개겠죠?)의 절반이라면 모두 매칭이 되었다 볼 수 있을 겁니다. 즉, 그룹의 숫자의 개수가 4개이고 매칭된 개수가 2개(7과 10, 11과 12)이면 모두 매칭이 되었다 보는 것이죠.

 

이분 매칭을 구하는 구체적인 알고리즘은 이전 문단에 걸어둔 링크를 타고 보면 알 수 있을 거에요! 이분 그래프와 이분 매칭을 이용해 아래의 코드로 성공하였습니다.

import sys
import math

def dfs(x):
    global Y
    global matched
    global visited
    if visited[Y.index(x)]: return False
    visited[Y.index(x)] = True
    for y in Y:
        if x + y in primes:
            if y not in matched or dfs(matched[y]):
                matched[y] = x
                return True
    return False

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
# X.sort()

# 소수 목록을 미리 준비
primes = []
for i in range(2, 2000):
    is_prime = True
    for j in range(2, i):
        if i % j == 0:
            is_prime = False
            break
    if is_prime: primes.append(i)
    else: continue

answers = []
for i in X:
    matched = {}
    if i == X[0]: continue
    if X[0] + i in primes:
        if N == 2:
            answers.append(i)
            break
        # print(i)
        # 첫번째 숫자와 현재 매치된 숫자를 제외한 새 리스트 생성
        Y = [x for x in X]
        del Y[0]
        del Y[Y.index(i)]
        matched = {}
        for y in Y:
            visited = [False for _ in range(len(Y))]
            dfs(y)
    
    # if matched: print(matched)
    if N != 2 and len(matched) == N - 2: answers.append(i)

if not answers:
    answers.append(-1)

answers.sort()

print(' '.join(list(map(str, answers))))