Algorithm] Closest Pair(최근접 점의 쌍 찾기)

Algorithm] Closest Pair(최근접 점의 쌍 찾기)

Closest Pair(말 그대로 최근접 점의 쌍 찾기)

XY 좌표 평면 상에 존재하는 점들 중, 가장 근접한 쌍을 골라내는 알고리즘이다.

가장 간단한 건, 한 점과 연결되는 모든 점들과의 거리를 계산하고

이를 바탕으로 최근접 거리를 탐색하는 것이다.

이 경우 N개의 점이 있다고 했을 때 N(N-1)/2의 비교,

Big O로는 N^2에 해당하는 시간복잡도가 소요된다.

점의 수가 100개 내외여도 꽤나 느려지는 것이 어마어마한 단점이다.

이 때 우리가 생각해볼 수 있는 것이 분할정복 방식(Divide and Conquer)인데,

부분 문제를 만들어서 계산과 비교 회수를 비약적으로 줄일 수 있다.

x축을 기준으로 정렬을 수행하고(이 때 정렬은 퀵정렬로 가정),

이를 기준으로 중앙점을 두고 그를 기준으로 반을 딱 나누어,

중앙을 기준으로 왼쪽 부분 문제와 오른쪽 부분 문제의 최고 근접 거리를 바탕으로

다시 중앙에서 범위를 좁혀나가는 방식으로 좁혀나가면서

후보군을 최대한 미리 추리는 방식을 사용하면 전부 비교하는 것보다 효율적으로 운영할 수 있다.

내가 '알기 쉬운 알고리즘'이라는 책을 통해서 이것을 접했고,

나는 의사 코드를 바탕으로 이를 C로 작성했다.

근데 두 가지 정도의 예외 사항에 봉착했다.

처음부터 부분를 나눌 수 없는 크기(n<=3)가 입력으로 들어온 경우,

중앙 값을 기준으로 양측의 최근접 거리 범위 점이 2개 미만이라

'거리'라는 것을 정의내릴 수 없는 경우.

이런 부분을 예외 처리하고,

도움이 되라고 부분 문제와 부분 문제 처리 결과를 출력하는 소스도 별도로 작성했다.

늘 말하는 것이지만, 나도 학생이고 과제로 제출한 미숙한 코드일 수도 있으니

별도의 오류가 존재할 수 있고 이에 대한 것은 디버깅 과정에서 잡아야 함을 미리 알리는 바이다.

늘 말하는 것이지만, 소스 코드는 참고용으로 올리는 것이다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
/* 구조체 타입 선언 */
typedef struct
{
    int x;
    int y;
} coord;
 
coord* minPairs = NULL; // 최근접점 저장 변수
double min = -1; // 최근접점 거리
 
/* 작은 값 리턴 */
double minNum(double a, double b)
{
    if (a<b)
    {
        return a;
    }
    else
    {
        return b;
    }
}
 
/* 배열에 담긴 점들을 출력하는 함수 */
void printPoint(coord* pair, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("(%d, %d)\n", (pair + i)->x, (pair + i)->y);
    }
    printf("\n");
}
 
/* 거리 계산 및 최접점 간 거리와 비교 */
double measureDistance(coord* a, coord* b)
{
    double distance;
 
    /* 거리 계산 */
    distance = sqrt(pow(a->x - b->x, 2) + pow(a->y - b->y, 2));
 
    /* 만약에 계산된 거리가 최소값인 경우,  */
    /* 최근접점 정보를 갱신 */
    /* 2,3쌍으로 구성된 문제에서 결정된 최소 사이즈가 */
    /* 최종 결과값인 경우에 대한 처리 부분 */
    if (min == -1 || distance < min)
    {
        *minPairs = *a;
        *(minPairs + 1) = *b;
        min = distance;
    }
    return distance;
}
 
/* 최접점을 구하는 함수 */
double ClosestPair(coord* pairs, int left, int right, int size)
{
    /* 부분 문제 출력 */
    printf("<<<부분 문제>>>\n");
    printPoint(pairs + left, size);
 
    /* 2쌍 */
    if (size == 2)
    {
        return measureDistance(pairs + left, pairs + right);
    }
    /* 3쌍 */
    else if (size == 3)
    {
        double distance1, distance2, distance3, min;
        distance1 = measureDistance(pairs, pairs + 1);
        distance2 = measureDistance(pairs + 1, pairs + 2);
        distance3 = measureDistance(pairs + 2, pairs);
 
        /* 최소값 리턴 */
        min = minNum(distance1, distance2);
        min = minNum(distance3, min);
        return min;
    }
    /* 4쌍 이상, 분할 작업 */
    else
    {
        /* 분할을 위한 중앙 인덱스 설정 */
        int mid = (left + right) / 2;
 
        /* 거리 범위, CPr, CPl에 대한 선언 */
        double distanceRange;
        double CPright, CPleft;
 
        /* 분할 시 최접점 거리 후보로 두고, 이를 범위로 잡음 */
        /* CPl, CPr 탐색 */
        CPleft = ClosestPair(pairs, left, mid, mid - left + 1);
        CPright = ClosestPair(pairs, mid + 1, right, right - mid);
        distanceRange = minNum(CPleft, CPright);
 
        /* CPl, CPr 출력 */
        printf("CPleft : %lf, ", CPleft);
        printf("CPright : %lf\n\n", CPright);
 
        /* 임시 저장 변수 동적 할당 */
        coord* pairsTmp = (coord*)malloc(sizeof(coord)*size);
        int cnt = 0;
 
        /* 부분 최소값 */
        double minSub = -1;
 
        /* 범위 내에 들어 있는 점들 임시 저장 */
        for (int i = left; i <= right; i++)
        {
            if (abs((pairs + i)->x - (pairs + mid)->x) < distanceRange)
            {
                (pairsTmp + cnt)->x = (pairs + i)->x;
                (pairsTmp + cnt)->y = (pairs + i)->y;
                cnt++;
            }
        }
 
        /* 범위 내 점들 출력 */
        printf("<< 범위 >>\n");
        printf("distanceRange : %lf\n", distanceRange);
        printPoint(pairsTmp, cnt);
 
        /* CPc 탐색 */
        for (int i = 0; i < cnt; i++)
        {
            for (int j = i + 1; j < cnt; j++)
            {
                /* 범위 거리와 범위 내 최단 거리 간 비교 */
                /* CPc와 범위 거리 비교해서 범위 거리 갱신 */
                minSub = minNum(distanceRange, measureDistance(pairsTmp + i, pairsTmp + j));
 
                /* 부분 최근접 거리가 설정된 범위보다 좁을 경우, 정보 복사 */
                if (minSub < distanceRange)
                {
                    /* distanceRange(CPl or CPr)보다 작은 거리값이 존재한다면, */
                    /* 이를 갱신해서 좀 더 빠르게 범위를 좁혀나갈 수 있음 */
                    /* 이 과정을 거친 distanceRange가 이 부분 문제의 최근접 거리 */
                    distanceRange = minSub;
                    if (minSub<min)
                    {
                        *minPairs = *(pairsTmp + i);
                        *(minPairs + 1) = *(pairsTmp + j);
                    }
                }
            }
        }
 
        /* CPc 출력 */
        if (minSub == -1)
        {
            printf("범위 내 CPc가 존재하지 않습니다.\n");
        }
        else
        {
            printf("CPc : %lf\n\n", minSub);
        }
        
        /* 동적 할당된 메모리 해제 */
        free(pairsTmp);
        
        /* 최근접 거리 리턴 */
        return distanceRange;
    }
}
 
/* 퀵정렬을 위한 비교 함수 */
int coordCompare(const void* a, const void* b)
{
    const coord *m, *n;
    m = (const coord*)a;
    n = (const coord*)b;
 
    if (m->x > n->x)
    {
        return 1;
    }
    else if (m->x == n->x)
    {
        return 0;
    }
    else
    {
        return -1;
    }
}
 
int main(void)
{
    int n; // 입력 케이스 크기
    coord* pairs = NULL; // 점을 입력 받는 변수
    int i;
 
    /* 좌표 개수 입력 */
    printf("입력할 좌표의 개수 : ");
    scanf_s("%d", &n);
 
    /* 입력 받은 좌표 개수 토대로 동적 할당 */
    pairs = (coord*)malloc(sizeof(coord)*n);
    /* 최접점쌍을 저장하기 위해 동적 할당 */
    minPairs = (coord*)malloc(sizeof(coord) * 2);
 
    /* 좌표 입력 */
    for (i = 0; i<n; i++)
    {
        scanf_s("%d%d", &(pairs + i)->x, &(pairs + i)->y);
    }
 
    /* 퀵정렬 */
    qsort(pairs, (size_t)n, sizeof(coord), coordCompare);
 
    printf("<<정렬 결과>>\n");
    printPoint(pairs, n);
 
    /* 최근접점 결과값 출력 */
    printf("최근접 거리 : %lf\n", ClosestPair(pairs, 0, n - 1, n));
    printf("<<최근접점>>\n");
    for (int i = 0; i < 2; i++)
    {
        printf("(%d, %d)\n", (minPairs + i)->x, (minPairs + i)->y);
    }
 
    /* 동적 할당된 메모리 해제 */
    free(pairs);
    free(minPairs);
    return 0;
}