[백준 Java] 14224번 작은 정사각형 2

💡문제

[Gold I] 작은 정사각형 2 - 14224

문제 링크

성능 요약

메모리: 12032 KB, 시간: 212 ms

---

🤔접근법

주어진 N개의 점에서 K개를 포함하는 최소로 작은 정사각형의 크기를 구하는 문제

범위 체크 및 시간복잡도 예상

• 2 ≤ N ≤ 100
• 1 ≤ K ≤ N
• -1,000,000,000 ≤ x, y ≤ 1,000,000,000
• $O(N^4)$까지도 가능하다.
• 가능한 좌표의 범위가 -10억 ~ 10억까지 이므로 최대로 가능한 사각형의 길이가 20억이여서 사각형 변의 길이를 1 ~ 20억 까지 모두 탐색할 순 없다.

풀이법

❌ 접근 방법. 완탐

점 N개에서 K개를 포함하는 가장 작은 정사각형을 만들기 위해서 변의 길이가 2 ~ 20억까지 모두 탐색해보면서 이 길이를 가지고 정사각형을 만들었을때 점이 K개가 포함되는지 확인하면 된다.
변의 길이가 2라고 했을 때
가장 작은 x 좌표는 -10억이고 가장 작은 y 좌표도 -10억이다.
그렇다면 이 좌표에서 변의 길이가 2인 사각형의 좌표는 (-10억, -10억), (-10억 , -10억 +2), (-10억 +2, -10억), (-10억 +2, -10억+2)가 된다. 정사각형 네 꼭짓점을 찍은 것이다.
이때를 범위로 잡고 N개의 점을 탐색하면서 범위 안에 들어가는지 확인하면 된다.
만일 이때 범위 안에 있는 점의 개수가 K개 보다 작다면 정사각형을 x좌표를 1씩 이동하며 다시 그 범위 내에 점들이 들어있는지 확인하고
그래도 들어 있지 않다면 y좌표를 1씩 증가하면서 그 범위내에 점들이 들어있는지 확인하면 된다.
그래도 들어 있지 않다면 사각형의 범위를 늘려야한다.
범위를 늘리기 위해서는 변의 길이를 1증가 시킨 후 다시 (-10억, -10억) 부터
모든 정사각형의 위치할 수 있는 좌표들을 탐색하며 그 범위내에 점들이 몇개들었는지 확인하면 된다.

그렇게 변의 길이를 늘려가며 탐색하다가 최초로 K개를 포함할 때 멈추게 된다.
그 이유는 K개를 포함하는 순간 그 이상의 변의 길이에서도 무조건 K개이상의 점을 포함할 수 있기 때문이다.

1. 변의 길이를 2부터 20억까지 늘려가면서 탐색하고 → $O(20억)$
2. 특정 변의 길이를 가진 정사각형이 위치할 수 있는 모든 구간을 탐색하고 → $O(20억 * 20억)$
3. 특정 구간에서 특정 변의 길이에서 점 N개가 범위 안에 있는지 탐색 → $O(N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(20억^3 * N)$ → 시간 초과

⭕ 접근 방법. 이분탐색 + 매개변수 탐색

위 풀이는 진짜 엄청 오래 걸릴 풀이이다.
저렇게 하면 얼마나 걸릴 지 궁금할 정도.

그치만 완탐 풀이에서 최적화가 가능한 부분이 몇몇 부분 보인다.
생각해보자.

위에서 말했다시피
사각형의 변의 길이를 늘려가며 탐색하다가 최초로 K개를 포함할 때 그 길이가 가장 작은 정사각형의 변의 길이 이다.
그 이상의 변의 길이에서도 무조건 K개 이상의 점을 포함할 수 있기 때문이라고 했다.

만약 변의길이가 7일때 K개를 최초 포함한다고 하자
이때 변의 길이에 따라 K개를 포함하느냐, 포함하지 않느냐로 표현하게 되면 아래와 같다.

길이	1	2	3	4	5	6	7	8	9	10	11
포함여부	x	x	x	x	x	x	o	o	o	o	o

표처럼 모든 변의 길이를 탐색할 때 딱 한번의 변화가 나타나게 된다.
변화가 나타난 후 그 이후의 값은 모두 동일한 결과를 가진다.
그렇다면 우리는 가장 최소가 되는 변의 길이 , 즉 포함여부가 O인 가장 작은 값을 찾으면 되고
이 말은 즉 포함여부가 O인 가장 왼쪽의 값이 된다.

이는 이분탐색으로 최적화가 가능하다. → $O(log20억)$

어떻게 하느냐면 탐색할 범위를 start ,end로 표시한 후

그 범위의 중간 값 mid의 포함여부가 x이다. 하면 mid 이전의 모든 값들은 모두 x 인게 확실하므로 탐색하지 않도 되니 start를 mid +1로 옮겨 탐색 범위를 줄일 수 있다.
또 그 start ~ end 범위에서 mid의 포함여부가 o이면 mid 이후의 모든 값은 모두 o이므로 탐색하지 않아도 된다. 우리는 o의 가장 작은 값을 찾을 거니까.
그래서 end = mid - 1로 줄여 탐색범위를 줄일 수 있다.
그렇게 범위를 줄여나가게 되면 마지막엔 7만 남게 될때
그 값이 가장 작은 정사각형의 변의 길이가 된다

그렇다면 문제는 포함여부를 어떻게 판별할 것인가 이다.

위 완탐 풀이에서는 좌표 평면에서 사각형이 위치할 수 있는 모든 경우를 다 보는 것이기 때문에 20억 *20억의 시간복잡도를 가지게 되었었다.

이는 사각형이 존재할 수 있는 위치를 탐색하는 것이 아니라
점이 최소 한 개 이상 존재하는 위치에서 범위를 탐색하면 된다.
즉 좌표평면을 모두 탐색하는 것이 아닌 점을 탐색하는 것이다.

이때 생각 해봐야 하는 것은 최소 정사각형에서의 "점의 위치"이다.
K개의 점을 가지는 최소 정사각형은 무조건 정사각형 선 위에 최소 1개 이상의 점을 가진다.
만일 라인 위에 점이 한개도 없다면 그건 정사각형과 점들 사이에 여유 공간이 존재한다는 의미이며 크기를 더 축소 시킬 수 있다는 의미이기 때문에 최소일 수가 없다.

그래서 우리는 점을 하나 선택하여 그 점으로부터 변의 길이 len을 가지는 정사각형을 만들어 그 정사각형 내에 점이 K개 존재하는 지로 바꾸어서 생각해 볼 수 있다.

이때 발생할 수 있는 문제는 선택한 점이 사각형의 어디에 위치할 것이냐 에 따라서 포함할 수 있는 점의 개수가 달라진다.

점의 좌표는 고정되어 있다. 사각형을 점을 기준으로 요리조리 움직여보자.

특정 점의 x좌표를 a라고 하고 y 좌표는 b라고 하자. 그리고 우리는 길이가 3인 사각형을 요리조리 움직여 볼 것이다.

이때 가정을 하나 할건데

점 x 좌표를 축으로 생각하고 그 축을 기준으로 왼쪽편(a-3 ~a)에는 점이 1개 존재하며 오른편(a ~ a+3)에는 점이 100개 존재한다고 가정하자. 포함할 점의 개수는 7개라고 하자.

그렇다면 점이 사각형의 가장 오른쪽상단에 존재한다고 했을 때

사각형의 가장 작은 x 좌표는 a - 3이고 가장 큰 x 좌표는 a이다.

그러면 우리는 보고있는 x 좌표의 범위는 a-3 ~ a 이다.

이때 사각형을 위아래로 움직여 보았을때

이때는 7개의 점을 포함하는 정사각형은 절대로 존재할 수 없다.

이유는 점을 기준으로 왼편엔 점이 1개밖에 존재하지 않기 때문에

사각형의 x 범위가 a-3 ~ a인 구간에서는 절대로 7개를 포함하는 정사각형을 만들 수 없기 때문이다.

그렇다면 이번엔 점이 왼편에 존재한다고 생각하자

사각형의 가장 작은 x 좌표는 a 이고 가장 큰 x 좌표는 a+3이다.

이때 사각형을 위아래로 움직여 보면 어디쯤에서는 점 7개를 포함하는 위치가 존재하지 않을까 생각할 수 있다.

이때 위에서 선택한 점을 무조건 포함하지 않아도 된다.

그점을 포함하지 않더라도 점 7개만 만족하면 되기 때문이다.

그래서 점 100개가 존재하는 a ~ a +3에서

그 점 100개를 탐색하면서 또다시 y좌표를 기준으로 y ~ y+3 에 점을 7개 포함하는지 확인하면 된다.

1. 2(start) ~ 20억(end)까지 이분탐색하여 mid를 정사각형의 길이로 선택 → $O(log20억)$
2. 모든 점을 탐색하며 x ~ x+len 범위 지정 일때 y ~ y +len 구간에서의 점의 개수 확인 → $O(N)$
3. 점이 K개 이상이이라면 end를 mid -1로 바꾸어서 탐색 범위 변경 → $O(N)$
4. 점이 K개 이하라면 start 를 mid+1로 바꾸어서 탐색 범위 변경 → $O(N)$
5. 이분탐색이 끝나고 결정된 최소 정사각형의 변의 길이 +2 의 제곱을 하여 정사각형의 넓이를 선택, 정사각형의 라인에 있는 점은 정사각형 내에 있는점이 아니기 때문에 정사각형의 크기를 키워준다.

여기서 추가로 왜 오른쪽만 보고 왼쪽은 안보냐 할 수도 있는데

점a…….점b 이런 상황에서

크기를 키워나가다 보면

점a—|...점b

점a—-|점b

점a—-점b-|

과 같이 결국 하나의 사각형 안에 들어가는 경우가 생기기 때문에 한쪽 방향으로 봐도 무방하다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N^3logN)$

---

🤯 1차 시도 FAIL

답을 봐서 문제를 푼 경우

• 해결이 되지 않은 부분 : 이분탐색까지는 접근 하였으나 len을 변의 길이로 하는 사각형들을 어떻게 다 탐색하지 생각나지 못하였다.
• 정답의 로직은 ?
  좌표 평면을 기준으로 다 탐색하는 것이 아닌 점을 기준을 탐색하는 것이 킥이었던거 같다.

😎SUCCESS

---

👩‍💻 코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_14224 {
    // 전역 변수 선언
    static int N; // 점의 개수
    static int K; // 정사각형 안에 포함되어야 하는 점의 최소 개수

    // 좌표를 나타내는 클래스
    static class Point{
        long x;
        long y;

        // 생성자
        public Point(long x, long y){
            this.x = x;
            this.y = y;
        }

        // 객체 출력을 위한 toString() 메서드 재정의
        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }

    // 점의 좌표 배열
    static Point[] points;

    // 메인 메서드
    public static void main(String[] args) throws IOException {
        // 입력 받기 위한 BufferedReader 및 StringTokenizer 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 점의 개수와 K값을 입력 받음
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // 점의 좌표를 저장할 배열 초기화
        points = new Point[N];

        // 점의 좌표 입력 받음
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            points[i] = new Point(x, y);
        }

        // 정사각형의 한 변의 길이를 이분 탐색으로 찾음
        long start = 0;
        long end = 2_000_000_000; // 최대 가능한 변의 길이
        long result  = 0; // 결과 변수 초기화

        // 이분 탐색
        while (start <= end) {
            long mid = (start + end) / 2L; // 중간 값 계산

            // 현재 길이(mid)로 만들 수 있는 정사각형이 K개의 점을 포함하는지 확인
            if(ok(mid)){
                result = mid; // 현재 길이로 만들 수 있는 정사각형이 K개의 점을 포함하면 결과 갱신
                end = mid - 1; // 탐색 범위를 왼쪽으로 이동
            } else {
                start = mid + 1; // 탐색 범위를 오른쪽으로 이동
            }
        }

        // 정답 출력
        long len = result + 2; // 정사각형의 한 변의 길이
        System.out.println(len * len); // 정사각형의 넓이 출력
    }

    // 길이가 len인 정사각형이 K개 이상의 점을 포함하는지 확인하는 메서드
    private static boolean ok(long len) {
        for (int i = 0; i < N; i++) {
            long leftX = points[i].x; // 정사각형의 왼쪽 x좌표
            long rightX = points[i].x + len; // 정사각형의 오른쪽 x좌표

            for (int j = 0; j < N; j++) {
                long bottomY = points[j].y; // 정사각형의 아래쪽 y좌표
                long topY = points[j].y + len; // 정사각형의 위쪽 y좌표

                int cnt = 0; // 정사각형 안에 포함된 점의 개수 카운트 변수

                // 모든 점에 대해 정사각형 안에 포함되는지 확인
                for (int k = 0; k < N; k++) {
                    // 점이 정사각형 안에 포함되면 cnt 증가
                    if (isInRange(k, leftX, rightX, bottomY, topY)){
                        cnt++;
                    }
                }

                // 정사각형 안에 포함된 점의 개수가 K개 이상이면 true 반환
                if(cnt >= K) {
                    return true;
                }
            }
        }
        return false; // 모든 경우에 대해 K개 이상의 점을 포함하지 않으면 false 반환
    }

    // 점이 주어진 범위 안에 있는지 확인하는 메서드
    private static boolean isInRange(int k, long left, long right, long bottom, long top) {
        return left <= points[k].x && points[k].x <= right && bottom <= points[k].y && points[k].y <= top;
    }
}