[BOJ] 14658 하늘에서 별똥별이 빗발친다 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
    static int N, M, L, K;
    static ArrayList<Pos> list = new ArrayList<>();
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        init();
        process();
        print();
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.add(new Pos(r, c));
        }
    }

    private static void process() {
        // 두개의 지점을 선택하고, 각각의 x 좌표와 y 좌표를 시작점으로 잡아서 리스트 탐색
        for (Pos p1 : list) {
            for (Pos p2 : list) {
                int cnt = 0;
                for (Pos pos : list) {
                    if (p1.r <= pos.r && pos.r <= p1.r + L && p2.c <= pos.c && pos.c <= p2.c + L) cnt++;
                }
                max = Math.max(cnt, max);
            }
        }
    }

    private static void print() {
        System.out.println(K - max);
    }

    static class Pos {
        int r;
        int c;

        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

📄 해설

물론 시간초과를 하는 것이 아니라면 쉽게 완전탐색을 수행하면된다.
그러나 본 문제는 범위가 굉장히 넓어, 최대한 적게 탐색을 수행해야한다. (개인적으로 이를 위한 접근이 어려웠다고 생각함

접근

• 두개의 지점을 사용해서 각각의 좌표를 추출해서 사용
• 추출해낸 좌표를 기준으로 탐색

과정

접근만 제대로 해내었다면 구현 과정 자체는 생각보다 심플한편

• 두개의 지점에서 각각 x 좌표와 y 좌표를 추출
• 추출해낸 두 좌표에 대해, 리스트에 존재하는 지점을 모두 탐색 (p1, p2 반복문)
• 현재 지점이 두 좌표의 범위내에 있으면 cnt 값 증가 (pos 반복문)