[알고리즘] sweeping-line 라인 스위핑을 통한 필터링

라인스위핑

• 스위핑 알고리즘이란? 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘.
• 일정 좌표, 축기준 정렬 한 뒤 일정 시점의 좌우 가장 가까운 두 점사이의 거리보다 멀리떨어진 점은 조사하지 않는 방식.
• 가지치기를 하겠다는 이야기다.(O(NlogN))

---

 

아래는 2261번 문제에 대한 분할정복 풀이.

import sys
input=sys.stdin.readline
INF=sys.maxsize
# 두 점 사이의 거리를 구하는 함수
def dist(a,b):
    return (a[0]-b[0])**2+(a[1]-b[1])**2

def divide(start,end):
    # 점 하나면 버림
    if start==end:
        return INF
    # 점 두개면 거리구해서 리턴
    elif end-start==1:
        return dist(arr[end],arr[start])
    # 분할
    mid=(start+end)//2
    # 받아온 거리값중 최솟값
    temp=min(divide(start,mid),divide(mid,end))
    # 후보군
    candicate=[]
    # 점을 순회하며 중간지점에서 x좌표 거리값이 최솟값 미만이면 조사군에 넣고
    for i in range(start,end+1):
        if (arr[mid][0]-arr[i][0])**2<temp:
            candicate.append(arr[i])
    # 조사군을 y축기준 정렬
    candicate.sort(key=lambda x:x[1])
    # 각 점의 y축 좌표에 대해 거리 계산 최솟값 미만이면 최솟값으로 갱신.
    lc=len(candicate)
    for i in range(lc-1):
        for j in range(i+1,lc):
            dy=(candicate[i][1]-candicate[j][1])**2
            if dy<temp:
                temp=min(temp,dist(candicate[i],candicate[j]))
            else:
                break
    return temp

n=int(input())
arr=[]
for i in range(n):
    arr.append(tuple(map(int,input().split())))
arr.sort()

print(divide(0,len(arr)-1))

---

라인 스위핑 풀이

한 점을 기준으로 각 x, y 좌표에서 최단 거리(d) 영역내에 존재하는 후보들을 추출한다.

후보들을 추출하는 과정 속에서 최단 거리(d) 를 갱신하는 방법을 반복한다.

1. x 오름차순으로 정렬
2. 두 점(array[0], array[1]) 사이의 거리를 최단 거리라고 가정
3. 최단 거리보다 작은 거리를 가지는 점들만 후보군에 삽입.
4. y축을 기준으로 정렬하고 x축에서 걸러진 후보자들을 순회 검사해 최단 거리를 갱신.

4번 과정 에서 정렬 시 후보자들 사이에서 (y - d) ~ (y + d) 영역을 구해야하는데 이는 이분탐색으로 해결 할 수 있다.

그래도 시간초과가 난다면

set 자료구조를 이용해서, 입력 단계에서 y값의 순서를 지켜주어, y값의 정렬을 하지 않고

또한 set은 삽입, 삭제, 탐색이 모두 O(lgN)이 걸리기 때문에, O(NlgN)이라는 시간으로 가장 가까운 두 점을 구할 수 있다.

---

라인스위핑(c++)

#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <limits.h>
using namespace std;
#define INF INT_MAX
typedef long long ll;
// 거리구하는 함수
ll getDist(pair<int,int> a, pair<int,int> b)
{
    int x1 = a.first;
    int y1 = a.second;
    int x2 = b.first;
    int y2 = b.second;
    return (x2-x1)*(ll)(x2 - x1) + (y2-y1)*(ll)(y2-y1);
}
// map객체
vector<pair<int, int>> vec;
map<pair<int, int>, int> m;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        vec.push_back({ x,y });
    }
    // x축 정렬을 하는 이유 ?
    // x축 정렬을 통해 x의축의 차이만으로 최대값 후보에서 여러 점들을 제외 시킬 수 있다.
    sort(vec.begin(), vec.end());
    // {y,x}으로 insert한 이유?
    // dx를 통해 if문으로 x축과의 거리는 처리 하였고,
    // map에 남아잇는 점들중에서 y축으로 lower_bound, upper_bound를 하기 위함이다.
    // = 0 인이 이유?
    // 어떤 값이든 크게 상관없지만 , INF보단 작고, -INF보단 커야한다.( lower_bound, upper_bound를 위해 )
    m[{vec[0].second, vec[0].first}] = 0;
    m[{vec[1].second, vec[1].first}] = 0;
    ll ans = getDist(vec[0], vec[1]);
    // pos = 0 부터, i = 2 부터인 이유?
    // 편의상 첫번째점과 두번째점을 (x축 정렬 기준 ) 을 기준으로 잡았다.
    // 밑의 코드의 for문을 돌리는대신 기준을 잡았다고 보면 된다.
    /*
    for(int i = 0 ; i < 2; i ++){
    ...
    }
    */
    int pos = 0;
    for (int i = 2; i < n; i++) {
        // pos부터 i-1번까지 i번째점과 비교를 한다.
        while (pos < i) {
            // x축간의 거리 차이
            int dx = vec[i].first - vec[pos].first;
            // pos( i 점 기준으로 현재 map 있는 가장 왼쪽 점 ) 과 i번째 점간의 x축 거리가
            // 더 작다면 pos점은 여전히 후보에 포함될 수 있다.
            if (dx * dx <= ans) break;
            // pos(i 점 기준으로 현재 map 있는 가장 왼쪽 점) 과 i번째 점간의 x축 거리가
            // 더 크다면 pos점은 더이상 더 작은 ans값을 만들어내지 못한다.( 후보에서 제외된다 )
            m.erase({ vec[pos].second,vec[pos].first });
            pos++;
        }
        // getDist 는 sqrt를 없이 반환했음으로...
        ll dis = sqrt(ans);
        // map에 남아있는 점들중에서
        // 현재 ans보다 작아 질 수 있는 후보 점들을 확인 하기위해 left, right를 찾고
        auto left = m.lower_bound({ vec[i].second - dis, -INF });
        auto right = m.upper_bound({ vec[i].second + dis, INF });
        // ans 갱신
        for (auto l = left; l != right; l++) {
        ans = min(ans, getDist( {l->first.second,l->first.first}, vec[i]));    
        }
        // i번째점은 당연히 뒤에 확인할게 있음으로 후보 점이 된다.
        m[{vec[i].second, vec[i].first}] = 0;
    }
    cout << ans << "\n";
    return 0;
}

출처: https://polohee81.tistory.com/47 [안틀린으로 코드로이드 코딩하기]

#pragma warning (disable: 4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
    Point() {
    }
    Point(int x, int y) : x(x), y(y) {
    }
    // set 등 자동으로 대소비교를 해주는 STL에서 구조체/클래스 등의 타입을 넣어주었을 때 발생하는 에러
    // 내부에서 데이터를 가지고 비교해야하는데 구조체 타입이기 때문에 연산을 할 수 없다.
    // 이를 해결하기 위해서 내부 정렬을 위한 방법을 지정해주면 된다.
    // 아래에서는 y값 순서대로 비교할 수 있게 하였다.
    bool operator < (const Point &v) const {
        if (y == v.y) {
            return x < v.x;
        }
        else {
            return y < v.y;
        }
    }
};
// x 값 비교
bool cmp(const Point &u, const Point &v) {
    return u.x < v.x;
}

// 두 점 사이 거리 제곱
int getDist(Point p1, Point p2) {
    return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

int main() {
    int n;
    scanf("%d", &n);
    vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a[i].x, &a[i].y);
    }
    sort(a.begin(), a.end(), cmp); // x 커지는 순으로 정렬
    set<Point> candidate = { a[0], a[1] };
    int ans = getDist(a[0], a[1]); // 처음 최소값은 0번 1번 거리로
    int start = 0;
    // candidate가 0번 1번으로 시작하니까 p는 2번부터 시작
    for (int i = 2; i < n; i++) {
        Point now = a[i];
        // 정해진 now를 기준으로 후보군과 길이 비교해서, 후보군 추리기
        while(start < i) {
            auto p = a[start];
            int dx = now.x - p.x;
            // 직선 거리가 정답보다 길다면 아예 후보군에 넣을 필요가 없음 
            if (dx*dx > ans) {
                candidate.erase(p);
                start += 1; // 시작점 앞당기기
            }
            else
                break;
        }
        int d = (int)sqrt((double)ans) + 1; // 길이 보정
        auto lower_point = Point(-100000, now.y - d); // 좌측 하단 
        auto upper_point = Point(100000, now.y + d); // 우측 상단
        // 하한값 위치, 상한값 위치
        auto lower = candidate.lower_bound(lower_point);
        auto upper = candidate.upper_bound(upper_point);
		// 이분탐색 시작
        for (auto it = lower; it != upper; it++) {
            // x값으로 추려진 candidate에서 
            int d = getDist(now, *it);
            // 지속적으로 ans를 갱신
            if (d < ans)
                ans = d;
        }
        // 사용된 now 역시 다시 후보군으로
        candidate.insert(now);
    }

    printf("%d\n", ans);

    return 0;
}

def dist(x1, x2):
    return (x1[0] - x2[0])**2 + (x1[1] - x2[1])**2

# 이론 블로그 참고
def solve(coords, N):
    # 점이 두 개일때는 두점 거리만 구하면 됩니다.
    if(N == 2):
        return dist(coords[0], coords[1])
    # 점이 세 개일때는 각 두점 사이의 거리를 구해서 최솟값을 구하면 됩니다.
    elif(N == 3):
        return min(dist(coords[0], coords[1]), dist(coords[1], coords[2]), dist(coords[0], coords[2]))

    mid = (coords[N//2][0] + coords[N//2-1][0]) // 2
    # x축을 기준으로 짧은 거리 d를 구합니다.최소거리 d보다 먼경우 제외.
    d = min(solve(coords[:N//2], N//2), solve(coords[N//2:], N//2))

    #  x 축 기준 두점 거리가 d보다 먼 경우는 제외합니다.
    short_check = []
    for subset in coords:
        if((mid - subset[0])**2 <= d):
            short_check.append(subset)
    short_check.sort(key = lambda x:x[1])

    if(len(short_check) == 1):
        return d
    else:
        y_check = d

        # y축을 고려해주어 y축 기준의 d보다 긴 경우는 전부 제외시켜 주어야 합니다.
        # 세 가지 경우는 제외합니다.
        for i in range(len(short_check) - 1):
            for j in range(i+1, len(short_check)):\
                # y축 기준, 기본적으로 최소 길이 d보다 사이 거리가 긴 경우 제외
                if(short_check[i][1] - short_check[j][1]) ** 2 > d:
                    break
                # 두 점 모두 왼쪽에 있는 경우
                elif(short_check[i][0] < mid and short_check[j][0] < mid):
                    continue
                # 두 점 모두 오른쪽에 있는 경우
                elif(short_check[i][0] > mid and short_check[j][0] > mid):
                    continue
                # 두 점은 필히 mid를 가로지르며 d보다 가까워야한다.
                y_check = min(y_check, dist(short_check[i], short_check[j]))

    return y_check


N = int(input())
coords = [list(map(int, input().split())) for _ in range(N)]

# 중복되는 점은 제거
coords_set = list(set(map(tuple,coords)))
if len(coords_set) != len(coords):
    print("0")
else:
    coords_set.sort() # sorted(coords, key=lambda x:-x[0])
    print(solve(coords_set, N))

파이썬 lower bound, upper bound 개념에 대해 알고가긴 해야할듯. 이분탐색때 자주나오는데 c++유저들은 라이브러리로 써서 정확히 뭐가 다른지.

이론은 이해가가는데 한번짜보면서 적용해야할듯.

 

참고