[백준 - 2261번] 가장 가까운 두 점 - Java //Wello Horld//

이번에는 BOJ의 2261번 문제 "가장 가까운 두 점" 문제를 풀어보도록 하자

문제는 간단한데, 풀이가 까다로운 문제이다. 먼저, 입력으로 점의 개수 n이 주어지고, 그다음 줄부터 n줄 만큼 각 점의 x, y 의 좌표가 공백을 사이에 두고 주어진다. 그리고 가장 가까운 두 점의 거리의 제곱값을 출력하면 되는 문제이다. 이 문제를 풀 때,  아래와 같이 하나하나씩 비교해주게 되면, 점이 최대로 많을 때, 100,000(개)가 존재하고, 시간 복잡도가 O(N^2)가 되기 때문에 거의 10,000,000,000(백억)번 정도 루프를 돌려주게되어서, 시간초과가 떠버린다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        Point[] points = new Point[n];
        long ans = Long.MAX_VALUE;
        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            points[i] = new Point(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
            for(int j = i - 1; j >= 0; j--){
                ans = Math.min(ans, (long)(Math.pow(points[j].x - points[i].x, 2) 
                	+ Math.pow(points[j].y - points[i].y, 2)));
            }
        }
        bw.write(ans + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}
class Point{
    long x, y;
    public Point(long x, long y){
        this.x = x;
        this.y = y;
    }
}

이러한 부분을 개선시키기 위해서 필요한 알고리즘은 라인 스위핑(Line Sweeping)기법이다. 입력으로 받아온 점들을 먼저, x값이 오름차순이 되도록 정렬을 시키고, TreeSet을 만들어 정렬시킨 점들을 차례대로 넣어주면서, 현재 최소값보다 크게 되면 해당 set에서 지워주고, 작을 가능성이 있으면 계산을 돌려주는 프로그램을 작성했다.

라인스위핑을 통해 문제를 해결하게 되면, 앞에서 완전탐색(Brute Force 기법)을 했을 때 보다, 필요없는 부분을 완전히 잘라내면서 계산을 진행하기 때문에 효율적으로(낮은 시간복잡도로) 계산을 할 수 있다. 성공한 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
		Point[] points = new Point[n];
		StringTokenizer st;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			points[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        //points를 x값이 오름차순이 되도록 정렬
        Arrays.sort(points, (a, b) -> (a.x - b.x));
        //TreeSet에 들어가는 Point의 y값이 같으면, x값이 오름차순이 되도록, 다르다면, y값이 오름차순이 되도록(y값을 기준으로 정렬)
		TreeSet<Point> set = new TreeSet<>((a, b) -> ((a.y == b.y) ? a.x - b.x : a.y - b.y));
		set.add(points[0]);
		set.add(points[1]);
		long answer = distSquare(points[0], points[1]);
		int start = 0;
		for (int i = 2; i < n; i++) {
            Point cur = points[i];
            //set에 있는 점들의 유효성 검사
			while (start < i) {
				Point point = points[start];
                long x = cur.x - point.x;
				if (x * x > answer) {
					set.remove(point);
					start += 1;
				} else {
					break;
				}
			}
            int d = (int) Math.sqrt((double) answer) + 1;
            //y값의 범위를 구해줌
			Point from = new Point(-10001, cur.y - d);
			Point to = new Point(10001, cur.y + d);
			for (Point point : set.subSet(from, to)) {
				long distance = distSquare(cur, point);
				answer = Math.min(answer, distance);
			}
			set.add(cur);
        }
        for(int i = 0; i < n; i++){
            bw.write(points[i].x + " " + points[i].y + "\n");
        }
        bw.write(answer + "\n");
        bw.flush();
        br.close();
        bw.close();
	}

	static long distSquare(Point A, Point B) {
		return (long)((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
	}
}
class Point{
    int x, y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

 

 

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

2261번: 가장 가까운 두 점