[백준, Java] 14224번, 작은 정사각형2, (이분 탐색)

문제 링크

14224번: 작은 정사각형 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 좌표 평면에는 N개의 꼭짓점이 존재합니다.

2. 정사각형의 꼭짓점은 모두 정수이며, 좌표 축과 평행해야 합니다.

3. 정사각형 경계 위에 있는 점은 정사각형 안에 있는 것이 아니다.

4. K개 점을 안에 담을 수 있는 정사각형의 최소 넓이를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 정사각형의 모든 시작점을 기준으로 이분 탐색을 통해 정사각형을 탐색합니다.

 

3. 탐색을 통해 얻은 정사각형의 최소 넓이를 결과로 출력합니다.

 

정사각형의 모든 시작점

 

좌표 평면에서 만들 수 있는 정사각형을 모두 만들어서 최소 넓이를 구할 수도 있지만, 문제 시간복잡도 조건에 만족하지 못합니다.

 

그러면, 좌표 평면에서 만들어야 하는 정사각형을 최소화하는 것이 매우 중요합니다.

 

 

아래와 같은 좌표 평면에 점이 존재할 때 정사각형을 해당 사각형 내부 안에 좌표들로 압축할 수 있습니다.

 

또한, 정사각형을 만들 때 최적화하게 만드는 좌표는 x좌표와 y좌표가 직선으로 만나는 곳입니다.

 

예를 들어, 좌하단의 좌표를 기준으로 정사각형을 만들면

 

실질적은 정사각형은 파란색이 됩니다.

 

조건에서 경계선에 있는 꼭짓점은 내부에 있는 것이 아니기 때문에 빨간선에서 정사각형을 만든 뒤에 x축, y축으로 1칸씩 이동하면 됩니다.

 

이분 탐색

 

이분 탐색은 정사각형의 최소 길이를 구하는 과정으로 이용합니다.

 

- 1,000,000,000 ≤ x, y ≤ 1,000,000,000이기 때문에 정사각형의 최대 길이는 2,000,000,002입니다.

 

▶ x축, y축을 나중에 늘릴예정이므로, 최대 길이는 2,000,000,000을 기준으로 탐색을 진행합니다.

 

즉, 이분 탐색 시작하는 데이터는

 

Start : 0

End : 2,000,000,000

 

이후, 이분 탐색을 통해서 정사각형의 길이가 mid일 때 꼭짓점을 K개 이상 포함하고 있으면 해당 정사각형의 넓이를 구해서 최소 넓이를 계산합니다.

 

넓이를 계산할 때에는 정사각형을 x축,y축으로 +1만큼 늘릴예정으로써 정사각형의 넓이를 구하는 식은 아래와 같습니다.

 

정사각형의 넓이 : (길이 + 1) × (길이 + 1)

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 2

 

M : 2

 

 

 

 

2. 정사각형의 모든 시작점을 기준으로 이분 탐색을 통해 정사각형을 탐색합니다.

 

정사각형 시작점 탐색

 

 

이분 탐색 진행

2개의 선을 포함하며, 이분 탐색으로 얻은 최소값 : 6

 

정사각형 넓이 (6 + 2) × (6 + 2) = 81

 

포함된 꼭짓점이 1개이므로, 만족하는 정사각형은 없습니다.

 

 

포함된 꼭짓점이 1개이므로, 만족하는 정사각형은 없습니다.

 

 

포함된 꼭짓점이 1개이므로, 만족하는 정사각형은 없습니다.

 

 

3. 탐색을 통해 얻은 정사각형의 최소 넓이를 결과로 출력합니다.

 

탐색이 끝났을 때, 정사각형의 최소 넓이는 81을 구하였습니다.

 

 

81

 

결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 점들의 좌표 정보를 띄어쓰기 기준 나눕니다.
• Set을 이용해서 좌표 평면에 중복되지 않도록 값들을 저장합니다.
• 좌표들이 직선으로 만나는 곳을 기준으로 정사각형에 대한 최소 넓이를 탐색하는 search함수를 실행합니다.
• 탐색을 통해 얻은 정사각형의 최소 넓이를 Bufferedwriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 이분 탐색을 통해서 정사각형의 최소 길이를 구합니다.
• checkPos함수는 정사각형 내에 K개의 점이 존재하는지 확인합니다.
• checkPos함수는 정사각형 내에 K개의 점이 존재한다면 최소 넓이를 비교합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    //좌표 평면 위치 관련 정의 객체
    static class Pos implements Comparable<Pos>{
        int x;
        int y;
        public Pos(int x, int y){
            this.x = x;
            this.y = y;
        }

        //y값 오름차순 정렬, y축 같을 때에는 x값 오름차순 정렬
        @Override
        public int compareTo(Pos o) {
            if(this.y == o.y){
                return this.x - o.x;
            }
            return this.y - o.y;
        }

    }
    static long result = Long.MAX_VALUE;
    //좌표 평면의 점 정보 저장 리스트
    static List<Pos> posList;
    //x,y좌표 중복 제거한 값(정사각형 시작점을 위한 Set)
    static Set<Integer> xSet, ySet;
    static int N;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        posList = new ArrayList<>();
        //입력되는 좌표 점 저장 
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            posList.add(new Pos(x, y));
        }
        xSet = new HashSet<>();
        ySet = new TreeSet<>();
        //좌표 정렬
        Collections.sort(posList);
        //X, Y좌표 중복없이 저장
        for(int i=0;i<N;i++){
            xSet.add(posList.get(i).x);
            ySet.add(posList.get(i).y);
        }
        //x,y축이 직선으로 만나는 점을 정사각형의 시작점으로 이분 탐색 진행
        for(int y : ySet){
            for(int x : xSet){
                search(x, y, K);
            }
        }
        //탐색이 끝난 뒤 정사각형 최소 넓이 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //이분 탐색으로 정사각형 최소 길이 구하는 함수
    static void search(int x, int y, int K){
        long start = 0;
        long end = 2000000000;
        while(start <= end){
            long mid = (start + end) / 2;
            //정사각형 길이가 mid일 때 점이 표함되는 개수 구하기.
            int cnt = checkPos(x, y, K, mid);
            //K개를 담지 못할 때
            if(cnt < K){
                start = mid + 1;
            }else{		//K개를 담을 수 있을 때
                end = mid-1;
            }
        }
    }
    //정사각형 길이가 주어졌을 때 K개의 점을 담을 수 있는지 확인 및 넓이 계산하는 함수
    static int checkPos(int x, int y, int K, long width){
        int cnt = 0;
        //정사각형 오른쪽 상단 꼭짓점 좌표
        long endX = x + width;
        long endY = y + width;
        //좌표 평면에 존재하는 점이 정사각형에 포함되는지 탐색
        for(int i=0;i<N;i++){
            //y값으로 오름차순 정렬했기 때문에 정사각형의 벗어나면 탐색을 종료
            if(posList.get(i).y > endY){
                break;
            }
            //정사각형 안에 포함될 때
            if(posList.get(i).y >= y && posList.get(i).x >= x && posList.get(i).x <= endX){
                cnt++;
            }
        }
        //정사각형에 포함되는 점이 K개 이상일 때
        if(cnt >= K){
            long len =  width + 2;	//x,y값 1칸씩 넓혀야 하기 때문에 +2
            result = Math.min(result, len * len);	//넓이 구해서 최소값 비교하기
        }
        return cnt;
    }
}