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

생각

홈 방범 서비스를 하는 업체가 있다. 방범 범위 K 값에 따라 아래와 같이 범위가 달라진다.



주어진 M은 집마다 지불하는 방범 비용이다. 아래와 같은 경우 방범 서비스의 유지 비용과
방범 서비스로 벌어들이는 비용의 차 즉, 업체의 이익은 다음과 같다.
K=3 이므로 3*3+(3-1)*(3-1)이 되어 운영 비용은 13이 되고
집들이 5개가 들어가 있으므로 M=3일 때, 3*5=15 가 되어
업체의 이익은 15-13 = 2 가 된다.

이경우 업체가 손해를 보지 않기 때문에 최대 방범 가능한 집의 수는 5개가 된다.
조건이 주어질 때, 업체가 손해 보지 않을 때 최대 집의 수를 출력하여라.

처음 생각

수학적인게 생각나면 좋겠지만, BFS를 통해 K 만큼 범위를 넓혀가면서 집의 개수를 찾는 완전 탐색이 떠올랐다.

▶ 풀이 후, 다른 풀이들을 보니 집의 위치를 저장해두고, 해당 좌표와 집들의 위치를 계산해서 풀이한 방법들이 있었다. 속도는 많이 차이나는건 아니였지만 메모리 부분에서는 수학적인 풀이가 3배정도 나았다.

▶ K의 범위가 정해져 있지 않아 처음 이부분에서 실수를 하였다. 업체가 손해를 보게되면 바로 종료를 해야하는 줄 알았는데 아래와 같은 2번 케이스가 있기 때문에 모든 조건을 살펴봐야겠다 느꼈다.
▶ 테스트 케이스로 주어진 다음같은 경우는 중앙에서 K=4 만큼 범위를 넓혀줘야 제대로 된, 값이 나오지만 업체가 손해를 볼 경우 바로 종료를 해버리면 K=1일 때 부터 손해로 인해 바로 종료가 되버린 것이였다.

1
7 7
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0

다음 생각

그렇다면 K를 다 살펴봐야한다. K의 조건을 어떻게 정해줄 까 생각을 하다 1인 자기 자신 칸부터 2N까지 진행하면 한 쪽 끝에서 시작을 해도 모든 칸을 다 덮을 수 있다. 따라서 1~2N 까지 조건을 주었다.

다다음 생각

이제 범위도 정했으니 해당 좌표에서 K 값에 따른 BFS를 진행하면서 집(1)을 발견했을 때 개수를 카운트 하여, 해당 K 값의 방범 유지 비용에 따른 집이 내는 방범 수익을 따저주면 된다.

다다다음 생각
BFS를 진행시 상 하 좌 우 4방향 탐색을 진행하므로 visited[][] 배열을 이용해서 방문 처리를 하면서 진행하게 된다. 그럼 K 값마다 이 값을 초기화 시켜주어야 하는데 이럴 경우 O(100N^5)이 되어 최악의 경우 3초를 넘겨버리게 된다.

▶ 테스트 케이스 50 , 모든 좌표를 보므로 N*N, 이에대해 K를 1~2*N 까지 진행하므로 2*N, 이 K 값마다 방문 배열 초기화를 위해 N*N이 들어가기 때문에 O(100N^5)이 되버린다.

▶ 이를 해결하기 위해 방문 배열을 초기화 하는 코드를 각 좌표의 BFS 탐색을 시작할 때만 초기화 하도록 바꿔주었다. BFS는 결국 한 칸 씩 나아가면서 조건이 만족되면 종료되는 것이기 때문에, 조건에 잡혔을 때의 좌표를 List에 저장해 놓았다가 그 List에 담긴 좌표들을 다음 K값에서 이어서 나아가도록 바꿔주었다. 이렇게 할경우 N*N이 사라지기 때문에 O(100N^3)이 되고, N이 최대 20 이므로 시간이 충분해진다.

다다다다음 생각

K를 진행해 나가면서 방문 초기화를 진행하지 않기 때문에, 집의 개수도 계속 이어서 세나갈 수 있도록 수정해주었다.

방안

1) K 값에 따른 범위가 딱 정해저 있으므로 이경우 (x,y)축의 거리를 따져 수학적으로 거리를 계산해서 구하면 좀 더 간단하고 효율적인 코드를 작성할 수 있다.

▶ 생각이 잘 안나는 부분이니 요럴 때라도 한 번씩 상기를 시켜주는게 좋은 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution {
    static int n,m;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        for(int i=1;i<=tc;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken()); // 하나의 집이 지불하는 비용
            arr = new int[n][n];
            visited = new boolean[n][n];
            for(int j=0;j<n;j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0;k<n;k++)
                    arr[j][k] = Integer.parseInt(st.nextToken());
            }
            max = 0;
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    solve(j,k);
            sb.append("#"+i+" "+max+"\n");
        }
        System.out.print(sb);
    }
    
    static int max;
    static boolean[][] visited;
    static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
    private static void solve(int x,int y) {
        Queue<Pair> queue = new LinkedList<>();
        List<Pair> list = new ArrayList<>();
        list.add(new Pair(x, y, 1));
        init(); // 새 좌표마다 초기화 해주기
        // 보안 구역 맵 끝까지 키우기 (한쪽 끝에서 시작해도 반대쪽까지 다 닿을 정도)
        int sum = 0;
        if(arr[x][y]==1) sum++;
        for(int i=1;i<2*n+1;i++) {
            for(Pair t:list)
                queue.add(t);
            list.clear();
            visited[x][y] = true;
            while(!queue.isEmpty()) {
                Pair t = queue.poll();
                if(t.cnt==i) {
                    // 새로 그리는게 아니고 +1 칸씩 시켜주는 것이므로 이어서 나가자
                    list.add(new Pair(t.x,t.y,t.cnt));
                    continue;
                }
                for(int j=0;j<4;j++) {
                    int tx = t.x+dir[j][0];
                    int ty = t.y+dir[j][1];
                    if(tx<0 || ty<0 || tx>=n || ty>=n) continue;
                    if(visited[tx][ty]) continue;
                    visited[tx][ty] = true;
                    if(arr[tx][ty]==1) sum++;
                    queue.add(new Pair(tx, ty, t.cnt+1));
                }
            }
            // 운영 비용이 더 많이 들면 처리 x
            if((sum*m)-(i*i+(i-1)*(i-1))<0){}
            else {
                // 아니라면 현 집 계수 최대값 계산
                max = Math.max(max, sum);
            }
        }
    }
    
    private static void init() {
        for(int i=0;i<n;i++)
            Arrays.fill(visited[i],false);
    }
    
    static class Pair{
        private int x,y,cnt;
        public Pair(int x,int y,int cnt){
            this.x = x;
            this.y = y;
            this.cnt = cnt; // 보안 구역 만들기 체크
        }
    }
}