Line Sweep 알고리즘 :: 마이구미

이 글은 Line Sweep 알고리즘을 다룬다.

Line Sweep, Sweep Line, 라인 스위핑 등과 같이 불려진다.

일반적으로 가장 가까운 두 점을 찾는 문제에서 출발한다.

다음 링크의 문제 풀이를 통하여 알고리즘을 설명할 것이다.

( 백준 2261번 "가장 가까운 두 점" )

참고 - https://www.acmicpc.net/blog/view/25

수 많은 점들 중에서 가장 가까운 두 점을 찾는 문제가 존재한다.

이러한 문제의 시나리오는 다음과 같다.

See the Pen line sweeping by leejunghyun (@mygumi) on CodePen.

순수한 접근으로 점들 중에서 가장 가까운 두 점을 찾는 방법은 간단하다.

모든 점들을 확인하면 된다.

하지만 이러한 경우 시간복잡도는 O(N^2) 이기에, 많은 시간이 걸린다.

이러한 문제를 해결하기 위해 Line Sweep 이라는 알고리즘을 사용한다.

이 알고리즘은 시간복잡도 O(NlogN) 까지 가능하게 해준다.

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

나타내는 의미는 다음과 같이 그림으로 표현할 수 있다.

위와 같이 후보들을 추출하는 과정 속에서 최단 거리(d) 를 갱신한다.

이러한 과정을 반복하게 된다.

기본적인 아이디어는 x, y 축을 나누어서 생각한 방식이다.

즉, 우선 x축을 먼저 고려한 후, y축을 고려하는 것이다.

전체적인 순서는 다음과 같다.

1. x 값이 증가하는 순으로 정렬한다.
2. 두 점(array[0], array[1]) 사이의 거리를 최단 거리라고 가정한다.
3. x축의 차이가 최단 거리보다 크다면 비교할 필요가 없기에 후보자를 걸러준다. 
4. y축을 기준으로 정렬된 후보자들을 통해 최단 거리를 갱신하게 된다.

4번의 과정인 최단 거리를 갱신하기 위한 과정에 있어, 후보자들 사이에서 (y - d) ~ (y + d) 영역을 구해야한다.

이 과정에서 시간 절약을 위해 이분 탐색을 사용하여 찾게 된다.

C++의 경우에는 lower_bound, upper_bound 를 통해 쉽게 구현이 가능하다.

JAVA의 경우에는 조금 더 복잡하지만 TreeSet 을 통해 구현할 수 있다.

본인의 경우에는 TreeSet의 tailSet 메소드를 Comparable 을 통해 오버라이딩했다.

// min => y - d, max => y + d
public int compareTo(Point p) {
    return min < p.y && max > p.y ? 1 : -1;
}

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/line-sweep/2261.java

private void solve() {
    int n = sc.nextInt();
    ArrayList<Point> list = new ArrayList<Point>();
    TreeSet<Point> candidate = new TreeSet<Point>(new ComparatorSet());
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        list.add(new Point(sc.nextInt(), sc.nextInt()));
    }
 
    Collections.sort(list, new ComparatorDescending());
 
    candidate.add(list.get(0));
    candidate.add(list.get(1));
    ans = distance(list.get(0), list.get(1));
 
    int start = 0;
    for (int i = 2; i < n; i++) {
        Point now = list.get(i);
 
        // x axis
        while (start < i) {
            Point pivot = list.get(start);
            int x = pivot.x - now.x;
 
            if (x * x > ans) {
                candidate.remove(pivot);
                start += 1;
            } else {
                break;
            }
        }
 
        int d = (int) Math.sqrt((double) ans) + 1;
        Point lower_point = new Point(now.y - d, now.y + d);
        SortedSet<Point> lower = candidate.tailSet(lower_point);
        Iterator<Point> it_lower = lower.iterator();
 
        while (it_lower.hasNext()) {
            Point p = it_lower.next();
            d = distance(now, p);
            if (d < ans) {
                ans = d;
            }
        }
        candidate.add(list.get(i));
    }
    System.out.println(ans);
}
 
public static int distance(Point p1, Point p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
 
static class ComparatorDescending implements Comparator<Point> {
    public int compare(Point p1, Point p2) {
        if (p1.x < p2.x) {
            return -1;
        } else if (p1.x == p2.x) {
            return 0;
        } else {
            return 1;
        }
    }
}
 
static class ComparatorSet implements Comparator<Point> {
    public int compare(Point p1, Point p2) {
        if (p1.y == p2.y) {
            if (p1.x < p2.x) {
                return -1;
            } else if (p1.x == p2.x) {
                return 0;
            } else {
                return 1;
            }
        } else {
            return p1.y < p2.y ? 1 : -1;
        }
    }
}
 
static class Point implements Comparable<Point> {
    int x;
    int y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
 
    public int compareTo(Point p) {
        return x < p.y && y > p.y ? 1 : -1;
    }
}