[백준 7573] 고기잡이(Java)

문제 링크 : https://www.acmicpc.net/problem/7573

이 문제는 단순한 완전탐색 방식으로 풀면 시간 초과 또는 메모리 초과가 발생합니다. 만약 물고기가 존재하는 전체 범위를 int의 이차원 배열로 설정한다면 N의 범위가 10000까지이기 때문에 메모리 초과가 발생하며, 모든 경우의 수를 반복문을 이용하여 탐색 시 역시 N의 범위가 10000까지여서 시간 초과가 발생합니다.

따라서 이 문제를 풀기 위해선 다른 접근이 필요합니다. 물고기 정보를 저장한 후 두 개의 물고기를 선택합니다. 이 때 두 물고기는 각각 그물의 x값과 y값 범위를 담당하며 이 범위 내에 물고기가 속하는 개수를 구하는 식으로 접근하면 됩니다. 모든 경우를 다 탐색하는 경우 물고기가 하나도 없는 공간을 탐색하게 되어 불필요한 계산을 진행하게 되는데 두 물고기를 선택한 후 이 물고기가 속한 범위 내에서 그물을 던지면 확정적으로 물고기를 잡을 수 있기 때문에 탐색 시간을 줄일 수 있습니다.

다음은 코드입니다.

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

public class Main{
    static int N,l,M;
    static int res = 0;
    static ArrayList<Pair> fish = new ArrayList<>();

    static void catchFish(int fish1, int fish2){
        // x,y값을 비교할 물고기 좌표 설정
        int y = fish.get(fish1).y;
        int x = fish.get(fish2).x;

        // 그물 범위 설정
        int v = 1;
        int h = (l - 2*v)/2;

        while(h>0){
            // 잡을 수 있는 물고기 수
            int cnt = 0;

            for(int i=0;i<M;i++){
                if(
                        // 두 물고기 중 한 물고기를 기준으로 그물 길이만큼의 x 길이 내에 물고기가 존재하는지 확인
                        x <= fish.get(i).x &&
                        fish.get(i).x <= x + h &&
                        // 두 물고기 중 한 물고기를 기준으로 그물 길이만큼의 y 길이 내에 물고기가 존재하는지 확인
                        y <= fish.get(i).y &&
                        fish.get(i).y <= y + v
                )
                    cnt++;
            }

            // 현재 물고기 수와 답과의 최대값 구하기
            if(res < cnt) res = cnt;

            // 다른 사이즈의 그물로 변환
            v++;
            h = (l - 2*v)/2;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        l = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 1,1 부터 시작
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            fish.add(new Pair(y,x));
        }

        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++){
                // 물고기 중에 2개를 고름
                catchFish(i,j);
            }
        }

        System.out.println(res);
    }
}

class Pair{
    int y;
    int x;

    Pair(int y, int x){
        this.y = y;
        this.x = x;
    }
}