Line Sweep 알고리즘 (백준 : 2261) JAVA

https://www.acmicpc.net/problem/2261

2261번: 가장 가까운 두 점

 

기본적인 방법

아래는 가장 기본적으로 N개의 점중 2가지를 선택해서 거리를 비교하는 방법이다. 가장 무식한 방법이며 
시간복잡도는 O(N^2) 이다 .따라서 N값이 조금이라도 커진다면 문제를 해결할 수가 없다.
그래서 필요한것이 LineSweep 이다.

package LineSweep;
 
import java.util.Scanner;
 
public class LineSweep1 {
 
    static int x[] = new int[100000];
    static int y[] = new int[100000];
    static int dist(int x1,int y1,int x2,int y2) {
        return (x1-x2) *(x1-x2) + (y1-y2) * (y1-y2);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        n =sc.nextInt();
        for(int i=0;i<n;i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        
        int ans = -1;
        
        for(int i=0;i<n-1;i++) {
            for(int j=i+1;j<n;j++) {
                int d = dist(x[i],y[i],x[j],y[j]);
                if(ans==-1 || ans> d) {
                    ans = d;
                }
            }
        }
        System.out.println(ans);
    }
    
}
 

 

 

알고리즘의 아이디어

먼저 x좌표순서대로 오름차순으로 정렬을 한다. 그다음 x좌표가 작은 것부터 하나씩 살펴본다.

 

1번 점부터 M-1 번점이 있을 때, 가장 가까운 점의 거리를 구한다. 그거리를 d 라고 한다면

 

이제는 d 안의 범위에 있는 점들이 후보점들이 될수가 있다.

 

 

 

처음 두점을 이용한 후보들을 선별하고 지우는 방법

package LineSweep;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
 
public class LineSweep2 {
    static class Point implements Comparable<Point> {
        int x, y;
 
        public Point(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
 
        @Override
        public int compareTo(Point o) {
            if (x > o.x) {
                return 1;
            }
            return -1;
        }
    }
 
    static int dist(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;
        n = sc.nextInt();
        ArrayList<Point> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            a.add(new Point(x, y));
        }
 
        Collections.sort(a);
 
        LinkedList<Point> candidate = new LinkedList<>();
        candidate.add(a.get(0));
        candidate.add(a.get(1));
 
        int ans = dist(a.get(0), a.get(1));
 
        for (int i = 2; i < n; i++) {
            Point now = a.get(i);
            for (Iterator<Point> it = candidate.iterator();it.hasNext();) {
                Point p = it.next();
                int x = now.x - p.x;
                if(x*x > ans) {
                   it.remove();
                }else {
                    int d = dist(now, p);
                    if(d < ans) {
                        ans = d;
                    }
                }
            }
            candidate.add(now);
        }
        System.out.println(ans);
 
    }
 
}
 

처음 알고리즘은 단숙 무식하게 모든 좌표2쌍을 탐색하는 거였다면 지금은 처음 정렬된 a[0] a[1] 를 기준으로 
거리를 잡는다. 이길이가 후보들 기준의 처음 길이이다.

그리고 i =2 번째부터 탐색을 한다.  (점이 두개인 예제는 ans 자체가 정답)

그리고 i -> M-1 좌표를 의미하는 것 

i번째 좌표에서 후보들을 본다. 그때 만약 기준은 ans 보다 후보의 x좌표와 i의 x좌표의 길이가 ans를 넘는다면

그 후보의 좌표는 i+1 번째에서도 당연히 ans보다 크게될것이다. 따라서 이값은 후보에서 제외해준다.

만약 ans 값보다 x*x 값이 적을 경우에는 실제 거리를 구해본다. 만약 실제 거리보다 작다면 ans값을 갱신한다.

그리고 후보군에 현재 i 좌표를 추가한다.

하지만 이방법은 candidate에 최대 n개의 후보들이 있고 결국에는 다조사해야하므로 O(N^2) 이다

X거리가 ans이하라면 후보탈락이다 Y도 마찬가지이다.

package LineSweep;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Scanner;
 
public class LineSweep3 {
    static class Point {
        int x;
        int y;
 
        public Point(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
 
    static class cmp implements Comparator<Point> {
 
        @Override
        public int compare(Point o1, Point o2) {
            // TODO Auto-generated method stub
            if (o1.x > o2.x) {
                return 1;
            }
            return -1;
        }
    }
 
    static class cmp2 implements Comparator<Point> {
 
        @Override
        public int compare(Point o1, Point o2) {
            // TODO Auto-generated method stub
            if (o1.y > o2.y) {
                return 1;
            }
            return -1;
        }
    }
 
    static int dist(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Point> a = new ArrayList<>();
 
        for (int i = 0; i < n; i++) {
            a.add(new Point(sc.nextInt(), sc.nextInt()));
        }
 
        Collections.sort(a, new cmp());
 
        ArrayList<Point> candidate = new ArrayList<>();
        candidate.add(a.get(0));
        candidate.add(a.get(1));
 
        int ans = dist(a.get(0), a.get(1));
 
        for (int i = 2; i < n; i++) {
            Point now = a.get(i);
            for (Iterator<Point> it = candidate.iterator(); it.hasNext();) {
                Point p = it.next();
 
                int x = now.x - p.x;
                if (x * x > ans) {
                    it.remove();
                }
            }
            Collections.sort(candidate, new cmp2());
 
            int d = (int) (Math.sqrt(ans)) + 1;
 
            Point lower_point = new Point(-1000000, now.y - d);
            Point upper_point = new Point(1000000, now.y + d);
            
            int lower = lowerBound(candidate,lower_point);
            int upper = upperBound(candidate,upper_point);
            
            for(int it = lower;it<=upper;it++) {
                d = dist(now,candidate.get(it));
                if(d < ans) {
                    ans =d;
                }
            }
            candidate.add(now);
        }
        System.out.println(ans);
 
    }
 
    public static int upperBound(ArrayList<Point> list, Point key) {
        int front = 0;
        int rear = list.size()-1;
        int mid;
        while(front<rear) {
            mid = (front + rear)/2;
            if(list.get(mid).y<=key.y) {
                front = mid+1;
            }else {
                rear =mid;
            }
        }
        
        return rear;
    }
 
    public static int lowerBound(ArrayList<Point> list, Point key) {
        int front = 0;
        int rear = list.size()-1;
        int mid;
        while(front<rear) {
            mid = (front + rear)/2;
            if(list.get(mid).y<key.y) {
                front = mid+1;
            }else {
                rear =mid;
            }
        }
        
        return rear;
    }
}
 

M-1 점의 좌표를 기준으로 i 점을 기준으로 y방향으로 +d , -d 범위 안에 좌표에서만 ans를 갱신해주면된다.

이것을 하기위해서는 y기준으로 정렬을 한번 해주고 upperbound 나 lowerbound를 이용해서 구하면된다.

-d는 lowerbound를 이용해서 +d upperbound를 이용해서 구하면된다 예를들어 -d +d 범위가 5 ~ 12 일때

좌표 y값이 1 2 4 6 6 6 7 9 11 12 13 13 13 일때 우리는 6 6 6 7 9 11 12 13 을 참조해야한다.

이때 lower바운드는 이상인수가 처음나타는 지점을 찾아주고 upperbound는 처음 초과하는 수를 찾아준다.

따라서 중복되는 수가 있어도 lower와 upper를 적절히 이용하면 범위의 수를 구할 수가 있다.

하지만 이알고리즘은 정렬하는데 시간을더써 위의 알고리즘 보다 훨씬느리다.

Tree 를 이용한 cnadidate 정렬

 

TreeSet 을 이용하면 반환 받는 시간과 삽입하는 하면서 정렬하는 시간 모두 log N 시간에 할수가 있다.
또한 TreeSet 안에는 subSet이라고 범위안에있는값을 반환하는 함수가 있기때문에 lower와 upper를 따로 구현할 피료가 없다. 하지만 시간초과다.

candidate에 들어있는 모든 점을 x길이를 비교하기때문이다. 또한 candidate는 y기준으로 정렬 되어있기 때문에 어디부터 어디까지고 x좌표의 거리차이가 d 이하인지를알수 없다.

x로 정렬된 a와  현재 i좌표까지의 후보들중에 있는 candidate는 y로 정렬되어 있다.

즉 set에는 입력받은 배열의 한구간이 들어갑니다. 그 구간의 끝점은 현재 i 이기 때문에 i-1이라는것을 알수있습니다.  또한 Scanser가 입력이 많이 느리기때문에 BufferedReader로 변경하도록 하겠습니다.

package LineSweep;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
 
import LineSweep.LineSweep4.Point;
 
public class LineSweep4 {
    static class Point implements Comparable<Point>{
        int x;
        int y;
        public Point(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Point o) {
            if(this.y>o.y)return 1;
            else if(this.y==o.y) {
                if(this.x>o.x) {
                    return 1;
                }
                return -1;
            }
            return -1;
        }
    }
    
    static class cmp implements Comparator<Point>{
 
        @Override
        public int compare(Point o1, Point o2) {
            if(o1.x>o2.x)
                return 1;
            return -1;
        }
    }
    
    
    static int dist(Point p1, Point p2) {
        return (p1.x - p2.x)*(p1.x-p2.x) + (p1.y-p2.y) *(p1.y-p2.y);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Point> a = new ArrayList<>();
        for(int i=0;i<n;i++) {
            a.add(new Point(sc.nextInt(), sc.nextInt()));
        }
        
        Collections.sort(a, new cmp());
        TreeSet<Point> candidate = new TreeSet<>();
        candidate.add(a.get(0));
        candidate.add(a.get(1));
        
        int ans = dist(a.get(0),a.get(1));
        
        for(int i=2;i<n;i++) {
            Point now = a.get(i);
            
            for(Iterator<Point> it = candidate.iterator();it.hasNext();) {
                Point p = it.next();
                
                int x = now.x - p.x;
                if(x*x > ans) {
                    it.remove();
                }
            }
            
            int d = (int)(Math.sqrt(ans) +1);
            Point lower_point = new Point(-100000,now.y - d);
            Point upper_point = new Point(100000,now.y + d);
            
            for(Point it : candidate.subSet(lower_point, upper_point)) {
                d = dist(now,it);
                if(ans > d) {
                    ans =d;
                }
            }
            candidate.add(now);
        }
        System.out.println(ans);
    }
}