[1007] 벡터 매칭

문제 링크 : https://www.acmicpc.net/problem/1007

1007 - 벡터 매칭

본문

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

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

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

입력

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

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

출력

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

제한

시간 제한	메모리 제한
2sec	512MB

• $2 \leq N \leq 20$
• $\lvert X \rvert , \lvert Y \rvert \leq 100000$

---

풀이

문제에서 원하는 점은 만들어진 모든 벡터의 합의 길이이므로, 만들어진 벡터 각각의 길이는 구하지 않아도 된다.

점의 개수는 총 $N$개이므로, 만들 수 있는 벡터는 총 $N/2$개이다. 이 때, 만들어진 벡터들 중 하나를 골라 각 점을 $a$, $b$라고 할 때, 그 벡터는 $a-b$나 $b-a$로 나타낼 수 있다. 이러한 벡터가 여러 개 있으므로, 그 벡터들의 표현을 모두 더하면 구하려는 해답을 얻을 수 있다.

정리하면 아래와 같다.

• 존재하는 점들 중 2개를 선택하여 벡터를 만들 수 있다.
  • 선택한 점을 각각 $a$, $b$라고 할 때, 만들어지는 벡터는 $a-b$ 또는 $b-a$이다.
  • 모든 점은 1번씩만 쓰이며, 같은 점은 존재하지 않는다.
• 구하려는 해답은 만들어진 모든 벡터의 합의 최솟값을 요구한다.
  • 즉, 모든 점을 2개씩 묶어 벡터를 만들고, 그 벡터의 합을 구하는 방법을 사용할 수 있다.
  • 먼저 선택한 점의 집합을 $A$, 이후에 선택한 점의 집합을 $B$라고 할 때, 구하려는 해답은 $\min{ \lvert \sum_{i=1}^{N/2} A_i - B_i \rvert }$로 나타낼 수 있다.
  • 위 수식은 $\min{ \lvert \sum_{i=1}^{N/2} A_i - \sum_{i=1}^{N/2} B_i \rvert }$로도 나타낼 수 있다. 이 수식이 구현 상 더 쉬워서 활용하려한다.

다만, 어떤 벡터의 집합이 합으로 나타냈을 때 가장 작은지는 계산할 수 있는 방법이 없다. 점의 개수 $N$의 크기가 $20$으로 작으므로, 모든 경우를 탐색하는 브루트포스 방식을 사용하여 각 조합을 구하는 방법을 사용하자.

브루트포스 방식은 각 점에 대해 선택되었나 선택되지 않았나를 정점으로 하는 트리 구조에서의 DFS 탐색을 사용하였다. 선택된 점은 1번 정점, 선택되지 않은 정점은 2번 정점으로 생각하고 각각 $A$, $B$ 집합에 소속시킨다. 그 이후 수식에 대입하여 해답을 찾는다.

• 참고 알고리즘 : 브루트포스, DFS-백트래킹

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 8

#include <math.h>  // sqrt
#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Node {
    long long x, y;
} ND;

#define INF 987654321987654321
#define MAX_IDX 20
ND arr[MAX_IDX];
bool comb[MAX_IDX];
int n;
long long result;
int threshold;

#define min(a, b) (((a) > (b)) ? (b) : (a))
#define get_len(a) ((a.x * a.x) + (a.y * a.y))

void reset() {
    for (int i = 0; i < n; ++i) {
        comb[i] = false;
    }
    result = INF;
    return;
}

void get_current_result() {
    ND vector_sum = (ND){0, 0};

    // if choosed, add them all
    // if not choosed, subtract them all
    for (int i = 0; i < n; ++i) {
        if (comb[i] == true) {
            vector_sum.x += arr[i].x;
            vector_sum.y += arr[i].y;
        } else {
            vector_sum.x -= arr[i].x;
            vector_sum.y -= arr[i].y;
        }
    }

    // calculate vector length
    result = min(result, get_len(vector_sum));
    return;
}

void make_combination(int cur, int choose_count) {
    if (choose_count == threshold) {  // combination created
        get_current_result();
        return;
    } else if (cur == n) {    // out of bound
        return;
    }

    // backtracking
    comb[cur] = true;
    make_combination(cur + 1, choose_count + 1);

    comb[cur] = false;
    make_combination(cur + 1, choose_count);

    return;
}

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        reset();
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            int x, y;
            scanf("%d %d", &x, &y);
            arr[i] = (ND){x, y};
        }

        threshold = (n >> 1);
        make_combination(0, 0);

        printf("%.7lf\n", sqrt(result));
    }
    return 0;
}

• arr[] : 입력받은 점들을 저장한 배열
• comb[] : 각 점을 선택하였는지를 저장한 배열
  • 선택되었다면 $A$, 선택되지 못했다면 $B$ 집합으로 점을 분배하는 역할
• threshold : 만들어진 벡터의 개수를 기록