C++로 점 집합의 모든 점을 지나는 단순 닫힌 경로 구현하기

문제 개요

평면상에 여러 개의 점으로 이루어진 집합이 주어졌다고 가정해 봅시다. 이때 우리의 목표는 모든 점을 한 번씩 지나가면서 스스로 교차하지 않는 단순 닫힌 경로(simple closed path)를 찾는 것입니다.

예를 들어 아래와 같은 점들이 있을 때, 이 점들을 모두 연결하는 하나의 닫힌 경로를 만들 수 있습니다.

알고리즘 접근 방법

닫힌 경로를 만들기 위해서는 다음 세 단계를 순서대로 수행하면 됩니다.

• 1단계: 점들 중 가장 왼쪽 아래(bottom-left)에 위치한 점을 찾아 기준점 P로 지정합니다.
• 2단계: 나머지 n−1개의 점을 기준점 P를 중심으로 반시계 방향 극각도(polar angle)를 기준으로 정렬합니다. 만약 두 점의 극각도가 같다면, 기준점 P로부터 거리가 더 가까운 점을 앞쪽에 배치합니다.
• 3단계: 정렬된 점 목록을 처음부터 끝까지 순회하면서 순서대로 경로를 연결합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Point {
    public:
    int x, y;
};
Point p0;
int euclid_dist(Point p1, Point p2) {
    return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
int orientation(Point p1, Point p2, Point p3) {
    int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
    if (val == 0) return 0; // 일직선상에 있는 경우
    return (val > 0)? 1: 2; // 시계 방향 또는 반시계 방향
}
int compare(const void *vp1, const void *vp2) {
    Point *p1 = (Point *)vp1;
    Point *p2 = (Point *)vp2;
    int o = orientation(p0, *p1, *p2);
    if (o == 0)
    return (euclid_dist(p0, *p2) >= euclid_dist(p0, *p1))? -1 : 1;
    return (o == 2)? -1: 1;
}
void findClosedPath(Point points[], int n) {
    int y_min = points[0].y, min = 0;
    for (int i = 1; i < n; i++) {
        int y = points[i].y;
        if ((y < y_min) || (y_min == y && points[i].x < points[min].x))
        y_min = points[i].y, min = i;
    }
    swap(points[0], points[min]);
    p0 = points[0];
    qsort(&points[1], n-1, sizeof(Point), compare); // 극각도 기준 정렬
    for (int i=0; i<n; i++)
    cout << "(" << points[i].x << ", "<< points[i].y <<"), ";
}
int main() {
    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},{0, 0}, {1, 2}, {3, 1}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    findClosedPath(points, n);
}

실행 결과

(0, 0), (3, 1), (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (0, 3),

동작 원리 설명

1. 기준점(Pivot) 선택

findClosedPath 함수는 먼저 y좌표가 가장 작은 점을 찾습니다. y좌표가 같은 점이 여러 개라면 그중 x좌표가 가장 작은 점을 선택합니다. 이렇게 선택된 점은 배열의 맨 앞으로 옮겨지며 전역 변수 p0에 저장됩니다.

2. 방향(orientation) 판별

orientation 함수는 세 점의 외적(cross product) 값을 계산하여, 세 점이 일직선상에 있는지, 시계 방향인지, 반시계 방향인지를 판별합니다. 이 정보는 극각도 정렬 시 점들의 순서를 결정하는 데 사용됩니다.

3. 극각도 정렬

compare 함수는 qsort에 전달되는 비교 함수로, 기준점 p0를 중심으로 각 점의 상대적 방향을 계산합니다. 두 점이 같은 방향에 있다면(일직선상), 기준점과의 유클리드 거리가 가까운 점을 우선 배치하여 경로가 교차하지 않도록 보장합니다.

시간 복잡도

이 알고리즘의 핵심은 정렬 단계이므로 전체 시간 복잡도는 O(n log n)입니다. 볼록 껍질(Convex Hull) 알고리즘(Graham Scan)과 유사한 정렬 기법을 활용하되, 내부 점들을 제거하지 않고 모든 점을 경로에 포함시킨다는 점이 다릅니다.