백준 1007번 백터 매칭 - 스위프트(Swift) 풀이

---

 

1. 각 점을 위치 벡터로 생각한다.
2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다.
3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다.

 

1. 각 점을 위치 벡터로 생각한다.

 먼저 각 점을 위치 벡터로 생각해줄 것이다.

 

2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다.

 다음과 같은 성질을 이용할 것이다. 

 두 점 A, B를 골라 A→B 또는 B→A로 가도록 벡터로 잇는 작업은, 두 점 A, B를 고른 뒤 두 점으로 가는 위치 벡터 중 하나를 역벡터로 만드는 작업이라고 할 수 있다.

 

3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다.

 결국 구해야 하는 것은 벡터 매칭에 있는 백터들을 모두 합한 벡터이고, 따라서 벡터 매칭에 있는 N/2개의 벡터의 각 성분을 더하기만 하면 된다. 백터 매칭에 있는 각 벡터의 성분은 다음과 같은 두 벡터의 합으로 이루어져 있다.

1. N개 점 중 한 점으로 가는 위치 벡터
2. N개 점 중 한 점으로 가는 위치 벡터의 역벡터

 따라서 최종 합벡터만 두고 보면 N개의 점으로 가는 위치벡터 중 절반만 역벡터로 만든 뒤 각 벡터의 성분을 모두 더한 것이 된다. 

 브루트포스로 절반을 역벡터로 만드는 모든 경우를 탐색한 뒤, 합벡터의 길이가 최소가 되는 경우를 찾으면 된다. N=20으로 매우 작으므로 O(2^N)으로도 시간 내에 돌아갈 수 있다.

반응형

---

import Foundation

let INF = 987654321.0
var N = 0
var points = Array(repeating: Vector(x: 0, y: 0), count: 20)
var minLength = INF

struct Vector {
    let x: Int
    let y: Int
    
    var length: Double {
        return sqrt(Double(x*x + y*y))
    }
    
    static func +(lhs: Vector, rhs: Vector) -> Vector {
        Vector(x: lhs.x + rhs.x, y: lhs.y + rhs.y)
    }
    
    static func -(lhs: Vector, rhs: Vector) -> Vector {
        Vector(x: lhs.x - rhs.x, y: lhs.y - rhs.y)
    }
}

func sumAllVectors(bitmask: Int) -> Vector {
    var sum = Vector(x: 0, y: 0)
    
    for i in 0..<N {
        if bitmask & (1 << i) == 0 {
            sum = sum - points[i]       // 마스킹된 N/2개 벡터는 역벡터 처리
        } else {
            sum = sum + points[i]
        }
    }
    
    return sum
}

func bruteForce(index: Int, count: Int, bitmask: Int) { // 절반을 역벡터로 만든다. AB = OB - OA이기 때문
    if index == N {
        if count == N / 2 {
            let sumVector = sumAllVectors(bitmask: bitmask)
            minLength = min(minLength, sumVector.length)
        }
        
        return
    }
    
    if count < N/2 { bruteForce(index: index+1, count: count+1, bitmask: bitmask | (1 << index)) }
    bruteForce(index: index+1, count: count, bitmask: bitmask)
}

func initTestcase() {
    minLength = INF
}

func solution() {
    var resultString = ""
    var T = Int(readLine()!)!
    
    while T > 0 {
        initTestcase()
        
        N = Int(readLine()!)!
        
        for i in 0..<N {
            let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
            let pair = Vector(x: input[0], y: input[1])
            points[i] = pair
        }
        
        bruteForce(index: 0, count: 0, bitmask: 0)
        
        resultString.write("\(minLength)\n")
        
        T -= 1
    }
    
    print(resultString)
}

solution()