[백준 9077] 지뢰제거 - Java 문제풀이

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

 

 

문제

지뢰제거를 위해서 새로운 장비가 투입되었다. 이 장비를 이용하면 10m × 10m 정사각형 범위 안(경계 포함)에 있는 지뢰를 한꺼번에 제거할 수 있다. 10,000m × 10,000m의 작업장에 묻힌 지뢰의 위치를 모두 알고 있다고 할 때, 이 장치를 효과적으로 사용하기 위해서 한 번 사용하여 제거할 수 있는 최대 지뢰 개수를 계산하는 프로그램을 작성하시오. 위의 그림은 아래 "예제 입력"의 세 번째 경우를 나타낸 것이다. 그림에서 보이는 정사각형 영역에 이 장비를 사용하면 다섯 개의 지뢰를 한꺼번에 제거할 수 있으며, 이 수가 한 번 사용하여 제거할 수 있는 최대 지뢰 개수이다.

 

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 지뢰의 개수를 나타내는 하나의 정수 N (4 ≤ N ≤ 100,000)이 주어진 다음, N개의 좌표가 한 줄에 하나씩 주어진다. 각 좌표는 0이상 10,000이하의 두 정수로 주어지는데, 첫 번째 정수는 x-좌표를, 두 번째 정수는 y-좌표를 나타낸다. 모든 정수 사이에는 한 칸의 공백이 존재한다. 같은 좌표에 두 개 이상의 지뢰는 존재하지 않으며, 지뢰의 크기는 무시할 정도로 작다고 가정한다. 

 

출력

각 테스트 케이스에 대해서 한 번에 가장 많이 제거할 수 있는 지뢰의 수를 출력한다.

풀이

접근법

1. 범위에 대해 확인해야하니까 누적합을 이용해보자
2. 수월하게 계산하기 위해 각 좌표를 +1하여 누적합을 해보자
3. 경계를 기준으로 제거를 한다면, 범위는 10이 아니라 11이 되는 것을 확인할 수 있다.

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        // 1. 범위에 대해 확인해야하니까 누적합을 이용해보자
        // 모든 테스트케이스에 대해서 새로운 배열을 만드는 것은 메모리를 많이 잡아먹으니까 재사용
        int[][] arr = new int[10010][10010];
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for(int tc=1;tc<=T;tc++) {
            for(int i=0;i<10010;i++) Arrays.fill(arr[i], 0);
            int N=Integer.parseInt(br.readLine());
            for(int i=0;i<N;i++) {
                st = new StringTokenizer(br.readLine());
                // 2. 수월하게 계산하기 위해 각 좌표를 +1하여 누적합을 해보자
                int a = Integer.parseInt(st.nextToken())+1;
                int b = Integer.parseInt(st.nextToken())+1;
                arr[a][b]++;
            }
            // 각 좌표까지의 2차원 배열의 누적합
            for(int i=0;i<10010;i++) {
                for(int j=0;j<10010;j++) {
                    if (i == 0 && j == 0) continue;
                    if (i == 0) {
                        arr[i][j] += arr[i][j-1];
                    } else if (j == 0) {
                        arr[i][j] += arr[i-1][j];
                    } else {
                        arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
                    }
                }
            }
            int ans = 0;
            // 3. 경계를 기준으로 제거를 한다면, 범위는 10이 아니라 11이 되는 것을 확인할 수 있다.
            for(int i=11;i<10010;i++) {
                for(int j=11;j<10010;j++) {
                    int cnt = arr[i][j] - arr[i-11][j] - arr[i][j-11] + arr[i-11][j-11];
                    ans = Math.max(ans, cnt);
                }
            }
            sb.append(ans).append("\n");
        }
        System.out.println(sb);

    }
}

 

사실 내 풀이방법은 완전탐색 방식이라 메모리와 시간이 많이 든다. 그래서 다른 분들의 풀이법을 참고하여 메모리를 반 이상 줄이거나 시간도 줄일 수 있다.