[Python] 백준 1007번 벡터 매칭 (골드2)

문제

평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속하는 모든 점은 한 번씩 쓰여야 한다.

벡터 매칭에 있는 벡터의 개수는 P에 있는 점의 절반이다.

평면 상의 점이 주어졌을 때, 집합 P의 벡터 매칭에 있는 벡터의 합의 길이의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.

테스트 케이스의 첫째 줄에 점의 개수 N이 주어진다. N은 짝수이다. 둘째 줄부터 N개의 줄에 점의 좌표가 주어진다. N은 20보다 작거나 같은 자연수이고, 좌표는 절댓값이 100,000보다 작거나 같은 정수다. 모든 점은 서로 다르다.

출력

각 테스트 케이스마다 정답을 출력한다. 절대/상대 오차는 10^-6까지 허용한다.

예제 입력 1

2
4
5 5
5 -5
-5 5
-5 -5
2
-100000 -100000
100000 100000

예제 출력 1

0.000000000000
282842.712474619038

예제 입력 2

1
10
26 -76
65 -83
78 38
92 22
-60 -42
-27 85
42 46
-86 98
92 -47
-41 38

예제 출력 2

13.341664064126334

 

---

풀이

벡터의 조합(Combination)을 고려해 계산하는 문제입니다.

Point

• 조합(Combination)
• 브루트 포스(Brute Force) 알고리즘

---

소스코드

import sys
import itertools
def input():
    return sys.stdin.readline()

def vec_size(vec):
    x,y = vec[0], vec[1]
    return (x**2+y**2)**(1/2)

def find_vector_combination(vectors):
    tot = [0,0]
    best_diff = float('inf')
    for vec in vectors:
        tot[0] += vec[0]
        tot[1] += vec[1]
    for combo in itertools.combinations(vectors, len(vectors)//2):
        combo_sum = [0,0]
        for vec in combo:
            combo_sum[0] += vec[0]
            combo_sum[1] += vec[1]
        diff = vec_size([tot[0]-2*combo_sum[0], tot[1]-2*combo_sum[1]])
        if diff < best_diff:
            best_diff = diff
    return best_diff

for _ in range(int(input())):
    n = int(input())
    points = []
    for _ in range(n):
        points.append(list(map(int,input().split())))
    print(find_vector_combination(points))

 

풀이가 바로 나오는 문제가 아닙니다.

 

네개의 점 P1, P2, P3, P4, P5, P6가 있다고 가정해 봅시다.

벡터 매칭의 한 예로는 [(P1-P2), (P3-P4), (P5-P6)]이 있을 것입니다.

 

최종적으로 최소화 하고 싶은 값은 |(P1-P2) + (P3-P4) + (P5-P6)| 의 크기입니다.

min |(P1-P2) + (P3-P4) + (P5-P6)| = min |(P1+P3+P5) - (P2+P4+P6)|

이런 식으로 음수가 붙는 점, 양수가 붙는 점으로 분할됩니다.

모든 점의 합(불변)을 tot = P1+P2+P3+P4+P5+P6 로 두면,

min |(P1-P2) + (P3-P4) + (P5-P6)| = min |(P1+P3+P5) - (P2+P4+P6)|

= min |(tot-(P2+P4+P6)) - (P2+P4+P6)| = min |tot - 2*(P2+P4+P6)|

입니다.

 

따라서, tot - 2*(P2+P4+P6) 값을 0에 가깝게 만드는 P2, P4, P6의 조합을 찾는 것을 목표로 할 수 있겠습니다.

 

Line 1~4

import sys
import itertools
def input():
    return sys.stdin.readline()

 

itertools는 모든 경우의 수에 따라 벡터들을 쉽게 조합해주는 라이브러리로 사용됩니다.

 

input()을 입력하는 라인 수가 많을 것으로 예상되면,

위와 같이 input() 함수를 sys.stdin.readline()으로 교체시켜주면, 실행시간이 빨라집니다.

'시간초과'의 원인이 된 적이 있기 때문에, 습관적으로 해두면 테스트 실행 한번을 아낄 수 있습니다

Line 6~8

def vec_size(vec):
    x,y = vec[0], vec[1]
    return (x**2+y**2)**(1/2)

 

벡터의 크기를 구하는 함수를 정의하여 나중에 귀찮지 않도록 합니다.

Line 10~25

def find_vector_combination(vectors):
    tot = [0,0]
    best_diff = float('inf')
    for vec in vectors:
        tot[0] += vec[0]
        tot[1] += vec[1]
    for combo in itertools.combinations(vectors, len(vectors)//2):
        combo_sum = [0,0]
        for vec in combo:
            combo_sum[0] += vec[0]
            combo_sum[1] += vec[1]
        diff = vec_size([tot[0]-2*combo_sum[0], tot[1]-2*combo_sum[1]])
        if diff < best_diff:
            best_diff = diff
    return best_diff

 

Line 10~ 15로 위에서 언급한 tot값을 우선 구해줍니다.

 

Line 16의 combo in itertools.combinations(vectors, len(vectors)//2)

는 vectors 라는 list에 저장되어 있는 벡터 중 절반을 추출하는 모든 조합을 구해줍니다.

 

추출된 벡터 조합의 벡터 합은 combo_sum(예시의 P2+P4+P6)에 저장됩니다.

 

각 조합에 대해 원하는 값인 diff = |tot - 2*(P2+P4+P6)|를 최소화해 줍시다.

이를 코드화 하면, diff = vec_size([tot[0]-2*combo_sum[0], tot[1]-2*combo_sum[1]])

 

마지막으로 문제에서 구하고 싶은 diff의 최솟값인 best_diff를 반환해 줍니다.

Line 26~31

for _ in range(int(input())):
    n = int(input())
    points = []
    for _ in range(n):
        points.append(list(map(int,input().split())))
    print(find_vector_combination(points))

 

 

input으로 Test Case의 개수를 받아 실행을 반복합니다.

 

각 Test Case 마다 점의 개수 n을 받아주고, points라는 list에 각 점을 저장해 줍니다.

 

위에서 정의한 함수에 points를 넣으면, 모든 경우의 수를 계산하는 Brute Force 방식으로 계산되어 결과를 도출합니다.