[백준] 1007 - 벡터 매칭 Python

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

1007번: 벡터 매칭

평면 상에 N 개의 점들 중 서로다른 두 점을 골라 만들수 있는 N/2 개 벡터들의 합 벡터의 길이의 최솟값을 구하는 문제다.

예를 들어, 4개의 점 (1,1), (2,4), (3,2), (3,4) 중에서 각각 2개씩 시작점과 끝점으로 골라 (1,3), (0,2) 라는 벡터를 만든다면, 이때 합 벡터는 (1,5) 가 되고, 합 벡터의 길이는 (1+25)^(1/2) 가 된다.

 

문제 조건에서 주어진 점들 사이 규칙이 별도로 없으므로 완전탐색을 생각한다.  벡터는 (끝점 - 시작점) 이므로, 시작점이 될 N/2 개의 벡터와 끝 점이 될 N/2 개의 벡터의 조합들을 구하고, 이들의 합 벡터중 길이가 최소인 것을 구하면 된다. 예를 들어, 시작점이 될 4개의 벡터가 1,2,5,4 번 이라면, (1,2,4,5), (2,1,5,4), (1,4,2,5) .. 등 여러 조합이 나올 수 있을 것이다.

 

여기서 구하는 것이 합 벡터라는 점을 주목해보자. 합이라는 의미는, 다시말해 순서가 상관이 없다는 것이다. 따라서 오름차순으로 딱 한번만 구해주고, 같은 케이스는 다시 구하지 않는 것으로 가지치기를 할 수 있다. 위 예시에서 (1,2,4,5) 만 구하는 것에 해당한다.

 

이를 이용해 백트래킹으로 N 개 점들 중 시작점이 될 N/2 개의 점들의 오름차순 조합을 구해준다.  끝점이 될 N/2 개의 점들은 별도로 구하지 않고, 합 벡터 = (끝점들의 합 - 시작점들의 합)  임을 이용한다. 주어진 N 개의 점들을 모두 더하면 (끝점들의 합 + 시작점들의 합) 이므로, 합 벡터 = (모든 점들의 합 - 2*시작점들의 합) 이다. 따라서 모든 점들의 합과, 시작점들의 합만 구한다면 합벡터를 구할 수 있다. 

 

코드로 나타내면 다음과 같다.

from sys import stdin


def dfs(level, start=0):
    global visited, v, ans, tp
    if level == N//2:
        ans = min(ans, (v[0]**2+v[1]**2)**(1/2))
        return
    for i in range(start, N):
        if (visited & 1 << i) == 0:
            visited |= 1 << i
            v[0], v[1] = v[0] - arr[i][0]*2, v[1] - arr[i][1]*2
            dfs(level+1, i+1)
            v[0], v[1] = v[0] + arr[i][0]*2, v[1] + arr[i][1]*2
            visited &= ~(1 << i)


T = int(stdin.readline())
for _ in range(T):
    N = int(stdin.readline())
    arr = []
    v = [0, 0]
    ans = float("inf")
    visited = 0
    for _ in range(N):
        x, y = map(int, stdin.readline().split())
        arr.append((x, y))
        v[0], v[1] = v[0] + x, v[1]+y
    dfs(0)
    print(ans)