[완전탐색] 2117. 홈 방범 서비스 (Java)

[SWEA] 2117. 홈 방범 서비스 (Java)

📌 풀이 과정

집의 위치를 저장 하고, 도시의 모든 격자 위치(i, j)를 중심으로
서비스를 제공할 수 있는 집의 갯수를 구하면 된다. (회사가 손해 보지 않는 경우에만)

손해를 보지 않는다?

서비스할 수 있는 집의 수(serviceHome)와 cost를 곱한 값에서 운영 비용을 뺀 결과가 0 이상인 경우

if(serviceHome * cost - loss >= 0){ // 보안회사가 손해보지 않는 경우
      answer = Math.max(answer, serviceHome);
}

💡 맨해튼 거리 활용

격자 형태의 공간에서 두 점 사이의 최단 거리를 말한다.
탐색 중심 좌표(i, j)에서 집 좌표(x, y)까지의 거리는 |i - x| + |j - y| 이다.

보안 서비스의 범위를 설정할 때, 중심 위치 (i, j)에서 거리 k 이내에 있는 모든 집들을 포함시켜야 한다.

즉, 맨해튼 거리의 특성상, 서비스 범위 k 내에 있는 집들은 중심 위치에서 |i - x| + |j - y| < k를 만족하는 집인 것이다.

💡 서비스(k) 범위

k의 크기에 따른 마름모를 살펴보면, 내부에 가장 큰 정사각형의 크기는

k=1일 때 1
k=2일 때 1
k=3일 때 3
k=4일 때 3
k=5일 때 5
k=6일 때 5

보안 서비스의 범위를 최대한 커버할 수 있도록
k는 N + 1까지 고려하면 된다.

✨ 제출 코드

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

public class 홈방범서비스_2117 {

    static int N, cost, answer;
    static int[][] map;
    static ArrayList<int[]> house;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for(int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 도시 크기
            cost = Integer.parseInt(st.nextToken()); // 지불 비용
            map = new int[N][N];
            house = new ArrayList<>();
            answer = 0;

            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if(map[i][j] == 1) house.add(new int[]{i, j}); // 집 위치 저장
                }
            }

            homeService();
            sb.append("#" + t + " " + answer + "\n");
        }
        System.out.println(sb);
    }

    static void homeService(){
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                for(int k = 1; k <= N+1; k++) {
                    int loss = calcOperatingCost(k); // 운영 비용
                    int serviceHome = 0; // 서비스 제공 받는 집

                    for(int[] home : house){
                        int x = home[0];
                        int y = home[1];

                        if(getDistance(i, j, x, y) < k) serviceHome++;
                    }

                    if(serviceHome * cost - loss >= 0){ // 보안회사가 손해보지 않는 경우
                        answer = Math.max(answer, serviceHome);
                    }
                }

            }
        }
    }

    static int getDistance(int i, int j, int x, int y){
        return Math.abs(i - x) + Math.abs(j - y);
    }

    static int calcOperatingCost(int k){
        return k * k + (k - 1) * (k - 1);
    }
}