점들중 가장 가까운 점을 구하는 알고리즘 질문입니다.

조회수 2801회

실행환경은 Bash를 통한 GCC컴파일러를 사용합니다. 16개의 점들중에 서로 가장 가까운 두 점의 거리를 구하는 프로그램을 만드려고 합니다.

#include <stdio.h>
#include <math.h>
#define NUM_OF_DOTS 16
#define MIN(x,y) ((x < y) ? x : y)
// 점 구조체
typedef struct {
    int x;
    int y;
}DOT;

// 거리 구하기
double distance (DOT a, DOT b) {
    double delta_x = a.x - b.x;
    double delta_y = a.y - b.y;
    return sqrt(delta_x * delta_x + delta_y * delta_y);
}

//세 수중 최소값
double min(double a, double b, double c) {
    int t;
    t = (a < b) ? a : b;
    t = (t < c) ? t : c;
    return t;
}

//합병정렬
void Merge(DOT *arr , int f, int mid, int l)
{
    DOT temp[16];

    int first1 = f; int last1 = mid;
    int first2 = mid+1; int last2 = l;
    int index = first1;

    for(;(first1<=last1)&&(first2<=last2); ++index)
    {
        if(arr[first1].x < arr[first2].x)
        {
            temp[index] = arr[first1];
            ++first1;
        }
        else
        {
            temp[index] = arr[first2];
            ++first2;
        }
    }

    for(; first1 <= last1; ++first1, ++index)
        temp[index] = arr[first1];
    for(; first2 <= last2; ++first2, ++index)
        temp[index] = arr[first2];
    for(index = f; index<=l; ++index)
        arr[index] = temp[index];
}

void Mergesort(DOT * arr , int first, int last)
{
    if(first < last)
    {
        int middle = (first+last)/2;
        Mergesort(arr,first,middle);
        Mergesort(arr,middle+1,last);
        Merge(arr, first,middle,last);
    }
}

//ClosestPair 함수
//Area는 점들이 모여있는 영역, start~end는 인덱스 기준으로 시작과 끝 범위.
//입력되는 Area 내의 점들은 x축 값을 기준으로 오름차순 되어야 함.
double ClosestPair(DOT * Area, int start, int end) { 
    //반복용 임시변수
    int i, j;
    //왼쪽 영역의 최소 길이
    double left_side;
    //오른쪽 영역의 최소 길이
    double right_side;
    //중간에 나뉘어지는 두 점의 길이
    double middle_side;
    //인덱스 범위 차 = (실제 개수) - 1
    int D = (end-start);
    //거리 지역변수
    double dist;

    if(D < 2) //점이 2개만 존재하면,
        return distance(Area[start], Area[end]);
    else { //점이 3개 이상이면 나눈다
        if(D % 2) { // 개수가 홀수이면
            left_side = ClosestPair(Area, start, (start + end)/2 );
            right_side = ClosestPair(Area, (start + end)/2 + 1 , end);
            dist = MIN(left_side, right_side);

            //중간거리 구하기
            //오른쪽 범위 구하기
            i = 0;
            while(1){
                double mid_distance_right = distance(Area[start + (D/2) - 1], Area[start + (D/2) + i]);
                if(mid_distance_right < dist) i++;
                else break;
            }
            //왼쪽 범위 구하기
            j = 0;
            while(1){
                double mid_distance_left = distance(Area[start + (D/2) - j], Area[start + (D/2)]);
                if(mid_distance_left < dist) j++;
                else break;
            }

            middle_side = distance(Area[start + (D/2) - j], Area[start + (D/2) + i]);

            return min(left_side, right_side, middle_side);
        }
        else {  //개수가 짝수이면
            left_side = ClosestPair(Area, start, start + (D/2));
            right_side = ClosestPair(Area, start + (D/2) + 1, end);
            dist = MIN(left_side, right_side);

            //중간거리 구하기
            //오른쪽 범위 구하기
            i = 0;
            while(1){
                double mid_distance_right = distance(Area[start + (D/2)], Area[start + (D/2) + i]);
                if(mid_distance_right < dist) i++;
                else break;
            }
            //왼쪽 범위 구하기
            j = 0;
            while(1){
                double mid_distance_left = distance(Area[start + (D/2) - j], Area[start + (D/2) + 1]);
                if(mid_distance_left < dist) j++;
                else break;
            }

            middle_side = distance(Area[start + (D/2) - j], Area[start + (D/2) + i]);

            return min(left_side, right_side, middle_side);
        }        
    }
}

int main() {
    DOT Area[NUM_OF_DOTS] = {{10,15}, {5,15}, {20,3}, {6,1}, {9,7}, {15,9}, {8,15}, {20,14}, {17,13}, {16,11}, {7,12}, {10,10}, {1,19}, {8,8}, {30,9}, {22,4}};
    Mergesort(Area , 0, 15); //정렬
    printf("%lf",sqrt(ClosestPair(Area,0,15)));
    return 0;
}

이 코드는 1.414214의 값이 출력되어 정상적으로 실행하는듯 보였지만, 점의 위치를 바꾸어도 계속 같은 값인 1.414214으로 출력됩니다.

혹시 어느 부분에서 잘못되었는지 확인할 수 있을까요?

  • (•́ ✖ •̀)
    알 수 없는 사용자

1 답변

  • DOT Area[NUM_OF_DOTS] = {{130,145}, {15,153}, {420,35}, {66,14}, {93,71}, {215,39}, {458,1345}, {201,114}, {137,143}, {156,161}, {77,812}, {910,170}, {16,195}, {448,38}, {320,93}, {242,34}};
    

    이런식으로 점을 전부 다 바꾸니 답이 다르게 나옵니다. 아마도 질문작성자님은, 점들 중 가장 가까운 거리를 결정짓는 두 점은 그대로 두고 다른애들만 바꿔서가 아닐까 싶습니다.

    근데 점이 16개밖에없는데 굳이 이렇게 힘들게 짜신 이유가 궁금하네요..

    #include <stdio.h>
    #include <math.h>
    #define NUM_OF_DOTS 16
    
    typedef struct{
        int y;
        int x;
    } DOT;
    
    int main() {
        int i, j;
        double min_dist = 1234567890;
        DOT Area[NUM_OF_DOTS] = {{10,15}, {5,15}, {20,3}, {6,1}, {9,7}, {15,9}, {8,15}, {20,14}, {17,13}, {16,11}, {7,12}, {10,10}, {1,19}, {8,8}, {30,9}, {22,4}};
    
        for(i = 0 ; i < NUM_OF_DOTS - 1 ; i++)
        {
            for(j = i + 1 ; j < NUM_OF_DOTS ; j++)
            {
                double delta_x = Area[i].x - Area[j].x;
                double delta_y = Area[i].y - Area[j].y;
                double dist = sqrt(delta_x * delta_x + delta_y * delta_y);
    
                if(dist < min_dist)
                    min_dist = dist;
            }
        }
    
        printf("%lf\n", min_dist);
        return 0;
    }
    
    
    • (•́ ✖ •̀)
      알 수 없는 사용자

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)