[SW Expert] [모의 SW 역량테스트] 2117번 홈 방범 서비스 (Java)

SW Expert [모의 SW 역량테스트] 2117번 홈 방범 서비스 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

 

 

마름모 구역 탐색 때문에 꽤나 고민했던 문제이다.

문제는 그렇게 어렵지 않다. 모든 경우의 수를 다 따져보면 되는 브루트 포스 문제이다.

프로그래머스의 자물쇠와 열쇠와 비슷한 문제이지만, 그보다 좀 더 복잡하다고 생각한다.

 

우선 마름모가 도시 밖으로 나갈 수 있으므로, 상하좌우로 패딩을 줘서 index가 도시 밖으로 나가지 않게끔 한다.

여기서는 전체 도시를 100 x 100 크기로 선언하여 (40,40)부터 입력을 받았다.

마름모를 탐색하는 방법은 여러가지가 있지만, 나는 맨 위의 좌표를 기준으로 탐색을 하였다.

맨 위의 좌표를 기준으로 하여 넓히면서 내려가다가,

내려간 횟수가 k-1번 이상이 되면 다시 좁히면서 내려갔다.

말은 쉽지만 되도록 깔끔하게 구현하고 싶어서 고민을 많이 했다.

 

마름모를 탐색하는 함수를 먼저 짠 후, 마름모의 기준 좌표를 움직이면서 모든 경우의 수에 대해서 탐색을 했다. (solution 함수)

 

한가지 팁이 있다면,

n = 20일 때 k는 21까지 탐색을 해줘야 400개의 모든 지역을 탐색할 수 있다. (테스트케이스 10번째)

 

 

코드

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

public class Main {
    private static int n, m, answer;
    private static boolean[][] map = new boolean[100][100];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            answer = 0;

            for (int i = 0; i < n; i++) { // 입력
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    map[i + 40][j + 40] = st.nextToken().equals("1");
                }
            }

            solution();
            System.out.println("#" + t + " " + answer);
        }
    }

    private static void solution() {
        for (int k = 1; k <= n + 1; k++) {
            int count = n;
            int opr = (int) Math.pow(k, 2) + (int) Math.pow(k - 1, 2); // 운영 비용

            for (int i = n - k; count > 0; i--, count--) { // n번 반복
                for (int j = 0; j < n; j++) {
                    int benefit = getBenefit(i + 40, j + 40, k, opr);
                    if(answer < benefit) answer = benefit;
                }
            }
        }
    }

    private static int getBenefit(int x, int y, int k, int opr) {
        int left = y, right = y, turn = k;
        int cnt = 0;

        for (int t = 0; t < 2 * k - 1; t++) { // 마름모 탐색
            for (int j = left; j <= right; j++) {
                if (map[x][j]) cnt++;
            }
            x++;
            if (turn-- > 1) {
                left--;
                right++;
            } else {
                left++;
                right--;
            }
        }

        int profit = cnt * m; // 서비스 제공받는 집들을 통해 얻는 수익
        return (profit - opr >= 0) ? cnt : -1; // 이익이 0보다 클 때 집의 개수 리턴
    }
}