swea 2117 홈 방범 서비스 Java (완전탐색)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu 

SW Expert Academy

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


N*N 크기의 도시에 홈방범 서비스를 제공하려고 한다.
홈방범 서비스는 운영 상의 이유로 [Fig. 1]의 파란색 부분과 같이 마름모 모양의 영역에서만 제공된다.

[Fig. 1]

또한, 홈방범 서비스를 제공하기 위해서는 운영 비용이 필요하다.
[Fig. 2]와 같이 서비스 영역의 크기 K 가 커질수록 운영 비용이 커진다.
운영 비용은 서비스 영역의 면적과 동일하며, 아래와 같이 구할 수 있다.
운영 비용 = K * K + (K - 1) * (K - 1)
운영 영역의 크기 K 는 1 이상의 정수이다.

 - K = 1 일 때, 운영 비용은 1 이다.
 - K = 2 일 때, 운영 비용은 5 이다.
 - K = 3 일 때, 운영 비용은 13 이다.
 - K = 4 일 때, 운영 비용은 25 이다.

 

[Fig. 2]

[Fig. 3]과 같이 도시를 벗어난 영역에 서비스를 제공해도 운영 비용은 변경되지 않는다.
[Fig. 3]의 경우 K = 3 이므로, 운영 비용은 13 이다.
 

[Fig. 3]

홈방범 서비스를 제공받는 집들은 각각 M의 비용을 지불할 수 있어, 보안회사에서는 손해를 보지 않는 한 최대한 많은 집에 홈방범 서비스를 제공하려고 한다.
도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다.
이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고,
그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라.


[예시]
예를 들어, [Fig. 4]과 같이 N이 8인 도시의 정보가 주어지고, 하나의 집이 지불할 수 있는 비용 M이 3이라고 생각해 보자.

 

[Fig. 4]

 

[Fig. 5]와 같이 서비스 영역 K = 2로 하여 홈방범 서비스를 제공할 때는 최대 3개의 집까지 서비스 제공이 가능하다.

이 경우 보안회사의 이익은 4가 되어 손해를 보지 않고 서비스 제공이 가능하다.

보안회사의 이익(4) = 서비스 제공받는 집들을 통해 얻는 수익(3*3) - 운영 비용(5)

 

[Fig. 5]

[Fig. 6]은 서비스 영역 K = 3으로 하여 홈방범 서비스를 제공할 때에 최대 5개의 집까지 서비스 제공이 가능한 경우 중 하나이다.

보안회사의 이익(2) = 서비스 제공받는 집들을 통해 얻는 수익(3*5) - 운영 비용(13)
 

[Fig. 6]

위의 예에서, 보안회사가 손해를 보지 않고 서비스 가능한 최대 집의 수는 5이며, 5가 정답이 된다.

[제약사항]
1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초
2. 도시의 크기 N은 5 이상 20 이하의 정수이다. (5 ≤ N ≤ 20)
3. 하나의 집이 지불할 수 있는 비용 M은 1 이상 10 이하의 정수이다. (1 ≤ M ≤ 10)
4. 홈방범 서비스의 운영 비용은 서비스 영역의 면적과 동일하다.
5. 도시의 정보에서 집이 있는 위치는 1이고, 나머지는 0이다.
6. 도시에는 최소 1개 이상의 집이 존재한다.


[입력]
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M이 주어진다.
그 다음 줄부터 N*N 크기의 도시정보가 주어진다. 지도에서 1은 집이 위치한 곳이고, 나머지는 0이다.

[출력]
테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,
그 때의 서비스를 제공 받는 집들의 수이다.

풀이

문제를 읽어보면 k의 범위를 설정해야 하는 것을 생각할 수 있을 것이다.

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

k=1일 때 1

k=2일 때 1

k=3일 때 3

k=4일 때 3

k=5일 때 5

k=6일 때 5

 

즉 문제에서 주어진 정사각형 n의 크기+1이 k의 최댓값이 된다.

k를 n+1로 두고, 1까지 줄여나가면서 k크기의 마름모 안에 home이 몇 개 들어있는지 구하고,

현재 k 마름모에서 home이 있는 경우 k마름모는 home을 처음 찾은 가장 큰 마름모이므로

이 k 크기의 마름모를 20*20사이즈 그래프의 0번 인덱스부터 중심점으로 탐색하여 최대 이익인 정답을 찾을 수 있다.

 

home의 위치 값을 따로 저장해 두고, 마름모 안에 home이 들어있는지 마름모의 중심 좌표와 home의 포지션의 맨하탄 거리가 k보다 작다면 마름모 안에 속한 home이다.

 

코드

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
class Solution {
 
    static int n,m;
    static int[][] graph;
    static int[][] homePos;
    static int homeCnt;
    static int k;
     
    static int solve() {
        int answer=0;
        //찾아도 바로 끝내면 안 되고 현재 k까진 다 돌려봐야 최댓값을 뽑을 수 있다.
        while(k-->0) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    int cnt=0;
                    //맨하탄 거리가 k보다 작다면 방범 서비스에 포함
                    for(int idx=0; idx<homeCnt;idx++) {
                        int r,c;
                        r = homePos[idx][0];
                        c = homePos[idx][1];
                        if(Math.abs(i-r)+Math.abs(j-c)<k)cnt++;
                    }
                    if(k*k+(k-1)*(k-1)<= cnt*m && answer<cnt)
                        answer = cnt;
                }
            }
            if(answer>0) return answer;
        }
        return 0;
    }
     
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            //input
            StringTokenizer tk = new StringTokenizer(br.readLine());
            n = Integer.parseInt(tk.nextToken());
            m = Integer.parseInt(tk.nextToken());
            k = n+2;
            graph = new int[n][n];
            homePos = new int[n*n][2];
            homeCnt=0;
            for(int i=0; i<n; i++) {
                tk = new StringTokenizer(br.readLine());
                for(int j=0; j<n; j++) {
                    graph[i][j] = Integer.parseInt(tk.nextToken());
                }
            }
            //solve
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(graph[i][j]==1) {
                        homePos[homeCnt][0]=i;
                        homePos[homeCnt++][1]=j;
                    }
                }
            }
            int answer = solve();
            //output
            bw.write("#" + t+ " " + answer +'\n');
        }
        bw.close(); 
    }
}