SWEA 모의 2117 홈방범서비스

SWEA 모의 2117 홈방범서비스

 

 

문제링크

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

SW Expert Academy

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

핵심 컨셉

고려사항

 * 서비스는 센터를 중심으로 마름모 형태로 운영됨
 * 서비스는 운영 비용이 발생: 비용은 서비스 영역의 면적과 동일
  -- 운영 비용 = K * K + (K - 1) * (K - 1) --> 이 비용은 면적에 따라 동일하기 때문에 탐색 하기 전에 미리 구해놓자!!
  -- 주의 사항: 서비스 영역 마름모가 지도를 벗어나더라도 비용은 동일하게 발생한다.
  -- 운영영역의 크기 k는 전체 영역을 커버하려는 경우 맨 구석에 배치한다고 할 때 최대 2N 까지가 필요하다.
 

* 센터 위치 선정
  -- 어느 곳에 센터를 놓았을 때 손해를 보지 않고 최대한 많은 집에 홈 방범 서비스를 제공하는 것이 목적이므로 이윤을 남길 필요는 없다.
  -- 어떤 지점에 놓아야 할지 모르기 때문에 모든 지역에 놓아봐야 한다.
 

* 서비스는 중심에서 동심원 처럼 넓어지므로 탐색은 센터를 중심으로 BFS 탐색
  -- 한 바퀴씩 돌면서 집이 발견되면 수익이 달라진다. 따라서 무조건 달리지 말고 한 바퀴씩 범위를 넓힌다.
  -- 탐색 과정에서 집을 발견하면 집*비용이 운영 비용을 초과하지 않는지 점검 - 출발점이 집일 수도 있는 점 주의!!

입력사항

 * 도시의 크기 N은 5이상, 20이하의 정수
 * 하나의 집이 지불하는 비용 M은  1 이상 10 이하의 정수이다. (1 ≤ M ≤ 10)

 * 도시의 정보에서 집은 1, 나머지는 0
 * 최소 1개 이상의 집이 존재

출력사항

 * 손해를 보지 않으면서 홈 방법 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때 서비스를 제공받는 집들의 수

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=jDMvRTVSQqg&feature=youtu.be

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package se.code.모의;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 4. 24.
 * @see https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu
 * @mem 87,000 kb
 * @time 393 ms
 * @caution
 * 모든 지점에 대해서 홈방범 서비스를 실시해본다. 이때 중앙 점을 중심으로 한 사이클씩 확장해가면서 비용이 수익을 초과하지 않는지 확인한다.
 * 따라서 bfs로 동작하면 되는데 사이클이 발견된 집에 따라서 유동적이므로 한 사이클씩 동작해야 하는게 포인트
 * 이때 최대 사이클은 어떤 모서리에서 시작할 때로 2N까지 간다.
 */
public class SWEA_모의_2117_홈방범서비스 {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int[] costMap;// 감시 면적 증가에 따른 비용 맵
    static int TC, N, M;
    static int MaxHouseCnt; // 최대 집의 개수
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));

        StringBuilder sb = new StringBuilder();

        TC = Integer.parseInt(br.readLine());
        StringTokenizer tokens = null;
        for (int t = 1; t <= TC; t++) {
            tokens = new StringTokenizer(br.readLine());
            N = Integer.parseInt(tokens.nextToken()); // 도시의 크기 (5 ≤ N ≤ 20)
            M = Integer.parseInt(tokens.nextToken()); // 집이 지불하는 비용 (1 ≤ M ≤ 10)
            map = new int[N][N];

            // 운영 범위에 대한 비용 초기화
            initCostMap();

            for (int r = 0; r < N; r++) {
                tokens = new StringTokenizer(br.readLine());
                for (int c = 0; c < N; c++) {
                    map[r][c] = Integer.parseInt(tokens.nextToken());
                }
            }

            MaxHouseCnt = Integer.MIN_VALUE;

            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    solve(r, c);
                }
            }

            sb.append("#").append(t).append(" ").append(MaxHouseCnt).append("\n");
        }
        System.out.println(sb);
    }

    static void initCostMap() {
        // 거리에 따라서 이 비용은 고정되어있다.
        // 설사 도시를 벗어난 영역에 서비스를 제공해도 운영 비용은 변경되지 않는다.
        // 운영영역의 크기 k는 그림을 그려보면 2N 까지가 필요하다.
        costMap = new int[map.length * 2];
        for (int k = 1; k < costMap.length; k++) {
            costMap[k] = k * k + (k - 1) * (k - 1);
        }
    }

    static void solve(int row, int col) {
        Queue<Home> q = new LinkedList<>();
        visited = new boolean[map.length][map.length];
        visited[row][col] = true;
        q.offer(new Home(row, col));

        // 시작 지점이 혹시 집이면..
        int houseCnt = 0;
        if (map[row][col] == 1) {
            houseCnt = 1;
        }

        int qSize = 0;
        int searchDepth = 1;// 감시 영역의 너비

        // 한 바퀴씩 돌면서 집이 발견되면 수익이 달라진다. 따라서 무조건 달리지 말고 한 바퀴씩 범위를 넓힌다.
        while (!q.isEmpty()) {

            if (houseCnt * M >= costMap[searchDepth]) {
                MaxHouseCnt = Math.max(MaxHouseCnt, houseCnt);
            }

            qSize = q.size();

            while (qSize-- > 0) {
                Home front = q.poll();

                for (int d = 0; d < dirs.length; d++) {
                    int nr = front.row + dirs[d][0];
                    int nc = front.col + dirs[d][1];

                    if (isIn(nr, nc) && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        q.offer(new Home(nr, nc));
                        // 만약 방문 지점이 집이면 개수 증가
                        if (map[nr][nc] == 1) {
                            houseCnt++;
                        }
                    }
                }
            }
            searchDepth += 1;
        }
    }

    static boolean isIn(int row, int col) {
        return 0 <= row && row < N && 0 <= col && col < N;
    }

    static class Home {
        int row, col;

        public Home(int row, int col) {
            super();
            this.row = row;
            this.col = col;
        }

        @Override
        public String toString() {
            return "Home [row=" + row + ", col=" + col + "]";
        }

    }

    private static String src = "10\r\n" +
                                "8 3\r\n" +
                                "0 0 0 0 0 1 0 0\r\n" +
                                "0 1 0 1 0 0 0 1\r\n" +
                                "0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 1 0 1 0 0\r\n" +
                                "0 0 1 1 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 1 0 1 0\r\n" +
                                "1 0 0 0 0 0 0 0\r\n" +
                                "7 7\r\n" +
                                "0 0 0 1 0 0 0\r\n" +
                                "0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0\r\n" +
                                "1 0 0 0 0 0 1\r\n" +
                                "0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0\r\n" +
                                "0 0 0 1 0 0 0\r\n" +
                                "10 5\r\n" +
                                "0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 1 0 0 0 0 0 1 1\r\n" +
                                "0 0 0 0 0 1 0 0 1 0\r\n" +
                                "0 0 0 0 0 1 1 0 0 0\r\n" +
                                "0 1 0 0 0 0 0 0 0 1\r\n" +
                                "1 0 0 1 1 1 0 0 0 0\r\n" +
                                "0 1 0 1 0 1 0 0 0 1\r\n" +
                                "0 0 0 0 0 0 1 0 0 1\r\n" +
                                "0 0 1 1 0 0 0 0 0 0\r\n" +
                                "0 0 0 1 0 0 1 1 0 0\r\n" +
                                "15 4\r\n" +
                                "0 0 0 1 0 0 0 0 0 0 0 0 0 1 1\r\n" +
                                "1 0 0 0 0 1 0 0 0 1 0 0 0 0 0\r\n" +
                                "1 0 1 1 0 1 0 0 1 0 0 0 0 0 1\r\n" +
                                "0 0 1 0 1 0 0 0 0 1 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 1 1 1 0 0 0 0 0 0 0\r\n" +
                                "0 1 1 0 0 0 0 0 0 0 1 1 0 1 0\r\n" +
                                "0 0 0 0 0 1 0 1 0 0 1 1 1 1 1\r\n" +
                                "0 0 1 0 0 0 0 0 0 0 0 0 0 0 1\r\n" +
                                "0 0 0 0 0 0 0 1 0 0 1 0 1 1 0\r\n" +
                                "0 1 0 0 0 1 0 1 1 0 0 0 0 0 0\r\n" +
                                "1 1 1 0 0 0 0 0 1 0 0 0 0 1 0\r\n" +
                                "1 0 1 0 0 1 0 1 0 0 1 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 1 1 1 0 1 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 1 0 0 0 1 0 0 1 1\r\n" +
                                "0 0 0 0 1 0 0 0 0 0 0 1 0 0 0\r\n" +
                                "15 3\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 1 0\r\n" +
                                "0 0 0 0 0 0 0 1 0 0 0 0 0 0 0\r\n" +
                                "1 0 0 0 0 0 1 0 0 0 0 0 1 0 0\r\n" +
                                "0 0 0 0 1 0 0 0 0 1 1 0 0 0 1\r\n" +
                                "0 1 0 0 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 0 1\r\n" +
                                "0 0 1 0 0 0 0 0 1 0 1 0 0 0 0\r\n" +
                                "0 0 0 0 1 0 0 0 0 1 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 1 0 0 0 0 0 0 0\r\n" +
                                "1 0 0 0 0 0 1 0 1 0 0 0 0 0 0\r\n" +
                                "0 1 0 0 0 0 1 0 0 0 1 0 0 1 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 1 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 1 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 1 0 0 0 1 0 1 0 0\r\n" +
                                "15 8\r\n" +
                                "0 0 1 0 0 0 0 0 0 0 0 0 0 0 1\r\n" +
                                "0 0 0 0 0 1 0 0 0 0 0 0 0 1 1\r\n" +
                                "0 0 0 0 1 0 0 0 1 1 1 0 1 0 0\r\n" +
                                "1 1 0 0 0 1 0 1 0 0 0 0 1 0 0\r\n" +
                                "0 1 0 0 1 0 1 0 1 0 0 0 0 1 1\r\n" +
                                "0 0 0 0 0 0 0 1 0 0 0 1 0 0 0\r\n" +
                                "1 0 0 0 1 0 0 0 1 0 1 0 1 0 1\r\n" +
                                "1 1 1 0 0 0 0 0 1 0 0 0 0 1 0\r\n" +
                                "1 1 0 0 0 0 0 0 1 0 1 0 1 0 0\r\n" +
                                "1 1 0 0 1 0 1 0 0 0 0 0 0 1 0\r\n" +
                                "0 0 0 0 0 0 0 0 1 0 0 1 1 0 1\r\n" +
                                "0 0 0 0 1 0 0 0 1 0 0 0 0 0 0\r\n" +
                                "0 1 0 0 1 1 0 0 0 0 0 0 0 0 1\r\n" +
                                "1 0 0 0 0 0 0 1 1 1 0 0 0 1 1\r\n" +
                                "1 0 0 0 0 1 0 0 0 0 0 1 0 1 1\r\n" +
                                "15 2\r\n" +
                                "1 0 1 1 0 1 1 1 0 1 0 0 0 0 0\r\n" +
                                "1 0 0 1 0 0 0 0 1 0 0 0 1 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 1 1 1 1 0 0 0\r\n" +
                                "1 0 0 0 0 0 0 0 0 0 0 1 0 1 1\r\n" +
                                "1 1 1 1 1 1 1 0 0 1 0 0 1 1 0\r\n" +
                                "0 1 0 1 0 0 0 0 0 1 1 0 1 1 0\r\n" +
                                "1 0 0 1 1 1 0 0 1 0 0 0 0 1 1\r\n" +
                                "0 1 1 1 1 1 0 1 0 1 0 0 0 0 1\r\n" +
                                "0 0 1 1 0 0 0 0 0 0 0 0 1 1 1\r\n" +
                                "0 1 1 1 0 0 0 1 1 0 0 1 0 0 1\r\n" +
                                "0 0 1 0 0 1 1 0 1 0 0 0 1 0 0\r\n" +
                                "1 1 1 1 1 0 0 1 1 0 1 1 1 1 1\r\n" +
                                "1 1 0 0 0 0 0 1 0 0 0 0 0 1 0\r\n" +
                                "1 1 0 1 0 0 0 0 0 1 0 0 0 0 1\r\n" +
                                "0 1 0 0 0 0 1 0 0 1 0 1 0 0 0\r\n" +
                                "20 4\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0\r\n" +
                                "1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1\r\n" +
                                "0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1\r\n" +
                                "0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1\r\n" +
                                "0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0\r\n" +
                                "0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0\r\n" +
                                "1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1\r\n" +
                                "0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0\r\n" +
                                "0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0\r\n" +
                                "0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0\r\n" +
                                "0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0\r\n" +
                                "0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0\r\n" +
                                "20 10\r\n" +
                                "0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1\r\n" +
                                "0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0\r\n" +
                                "1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0\r\n" +
                                "0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\r\n" +
                                "0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0\r\n" +
                                "1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0\r\n" +
                                "0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0\r\n" +
                                "0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0\r\n" +
                                "0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0\r\n" +
                                "1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0\r\n" +
                                "0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0\r\n" +
                                "0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0\r\n" +
                                "0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 1\r\n" +
                                "0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0\r\n" +
                                "0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0\r\n" +
                                "20 3\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\r\n" +
                                "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1";


}