알고리즘/SWEA
SWEA 모의 2117 홈방범서비스
- -
SWEA 모의 2117 홈방범서비스
문제링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.
핵심 컨셉
고려사항
* 서비스는 센터를 중심으로 마름모 형태로 운영됨
* 서비스는 운영 비용이 발생: 비용은 서비스 영역의 면적과 동일
-- 운영 비용 = K * K + (K - 1) * (K - 1) --> 이 비용은 면적에 따라 동일하기 때문에 탐색 하기 전에 미리 구해놓자!!
-- 주의 사항: 서비스 영역 마름모가 지도를 벗어나더라도 비용은 동일하게 발생한다.
-- 운영영역의 크기 k는 전체 영역을 커버하려는 경우 맨 구석에 배치한다고 할 때 최대 2N 까지가 필요하다.
* 센터 위치 선정
-- 어느 곳에 센터를 놓았을 때 손해를 보지 않고 최대한 많은 집에 홈 방범 서비스를 제공하는 것이 목적이므로 이윤을 남길 필요는 없다.
-- 어떤 지점에 놓아야 할지 모르기 때문에 모든 지역에 놓아봐야 한다.
* 서비스는 중심에서 동심원 처럼 넓어지므로 탐색은 센터를 중심으로 BFS 탐색
-- 한 바퀴씩 돌면서 집이 발견되면 수익이 달라진다. 따라서 무조건 달리지 말고 한 바퀴씩 범위를 넓힌다.
-- 탐색 과정에서 집을 발견하면 집*비용이 운영 비용을 초과하지 않는지 점검 - 출발점이 집일 수도 있는 점 주의!!
입력사항
* 도시의 크기 N은 5이상, 20이하의 정수
* 하나의 집이 지불하는 비용 M은 1 이상 10 이하의 정수이다. (1 ≤ M ≤ 10)
* 도시의 정보에서 집은 1, 나머지는 0
* 최소 1개 이상의 집이 존재
출력사항
* 손해를 보지 않으면서 홈 방법 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때 서비스를 제공받는 집들의 수
동영상 설명
1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.
소스 보기
동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 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";
}
소중한 공감 감사합니다