만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 1017 소수 쌍

23 Jun 2021

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

수의 리스트가 주어졌을 때 각 쌍의 합이 소수가 되게 하려고한다. 이 때 모든 수를 다 짝지을 수 있는 경우 중에서 첫번째 원소가 짝지은 수를 오름차순으로 나타내는 문제이다.

두 수의 합이 소수가 되려면 2를 제외하고는 모두 소수가 홀수라는 점을 이용해야한다. 리스트 내의 수는 중복이 될 수 없으므로 2가 소수 쌍으로 나타날 수는 없다. 따라서 모든 소수 쌍은 짝수 1개와 홀수 1개의 합으로 이루어져야 한다. 이렇게 되니 주어지는 수들을 홀수 짝수 그룹으로 나누는데 첫번째 원소가 A 그룹의 첫번째 원소가 되도록 그룹을 나누자.

for i in num {
    if num[0]%2 == i%2 {
        numA.append(i)
    }
    else {
        numB.append(i)
    }
}

이제 A그룹과 B그룹 간의 이분 매칭을 해서 전체의 절반에 해당하는 매칭이 이루어지는지 확인하면 된다. 이 때 유의할 점으로는 A그룹의 첫번째 원소의 매칭은 dfs 함수 내에서 고정시켜주고 진행해야 한다. 또한 두 수의 합이 소수인 경우에만 간선이 존재한다고 생각하고 진행해야한다.

func dfs(nodeA: Int) -> Bool {
    for nodeB in 0..<n/2 where nodeB != pick { 
    // pick은 첫번째 원소와 매칭된 정점을 의미한다.
        if visited[nodeB] {
            continue
        }
        if Prime[numA[nodeA] + numB[nodeB]] {
        // 두 수의 합이 소수인 경우에만 진행
            visited[nodeB] = true
            if matchB[nodeB] == -1 || dfs(nodeA: matchB[nodeB]) {
                matchB[nodeB] = nodeA
                return true
            }
        }
    }
    return false
}

let n = Int(readLine()!)!
let num = readLine()!.split(separator: " ").map{Int(String($0))!}
var matchB:[Int] = Array(repeating: -1, count: n/2)
var visited:[Bool] = Array(repeating: false, count: n/2)
var numA:[Int] = []
var numB:[Int] = []
var Prime:[Bool] = Array(repeating: true, count: 2001)
var pick = 0

func dfs(nodeA: Int) -> Bool {
    for nodeB in 0..<n/2 where nodeB != pick {
        if visited[nodeB] {
            continue
        }
        if Prime[numA[nodeA] + numB[nodeB]] {
            visited[nodeB] = true
            if matchB[nodeB] == -1 || dfs(nodeA: matchB[nodeB]) {
                matchB[nodeB] = nodeA
                return true
            }
        }
    }
    return false
}


for i in 2...50 {
    if Prime[i] {
        var idx = 2*i
        while idx <= 2000 {
            Prime[idx] = false
            idx += i
        }
    }
}

for i in num {
    if num[0]%2 == i%2 {
        numA.append(i)
    }
    else {
        numB.append(i)
    }
}

if numA.count != numB.count {
    print(-1)
}
else {
    var success:[Int] = []
    for j in 0..<n/2 {
        if Prime[numA[0] + numB[j]] {
            pick = j
            matchB = Array(repeating: -1, count: n/2)
            var count = 1
            for i in 1..<n/2 {
                visited = Array(repeating: false, count: n/2)
                if dfs(nodeA: i) {
                    count += 1
                }
            }
            if count == n/2 {
                success.append(numB[j])
            }
        }
    }
    success.sort{$0 < $1}
    var str = ""
    for i in success {
        str += "\(i) "
    }
    print(success.count > 0 ? str : "-1")
}

Related posts