[모의 SW 역량 테스트] 홈 방범 서비스
1. 핵심 개념 및 근거
핵심 알고리즘: 완전 탐색 & 맨해튼 거리
- 사용 개념: 모든 가능한 중심점 (r, c)에 대해, 가능한 모든 서비스 운영 크기 K를 시도합니다.
- 근거: 지도의 크기(N)가 최대 20으로 매우 작습니다. 특정 위치에서 거리 k 안에 있는 집들을 찾는 과정은 O(N^2) 내에 해결 가능하므로, 전체 탐색이 가장 확실한 방법입니다.
- 자료구조:
- 2차원 배열: 지도 정보 저장
- 리스트: 집의 좌표만 따로 저장하여 탐색 효율을 높임
- 시간 복잡도
- 중심점의 개수(N^2) X 운영 크기(N+1) X 집의 개수(N^2)
2. 추론 과정
- 키워드 1: 마름모 모양의 영역
- 격자판에서 중심점 (r, c)로부터 거리가 k-1 이하인 지점들의 집합입니다.
- 맨해튼 거리: ( $\left\lvert r1 - r2 \right\rvert$ + $\left\lvert c1 - c2 \right\rvert$ < k) 공식을 떠올리게 합니다.
- 키워드 2: 손해를 보지 않으면서
- 지불 비용 M X 집의 개수 - 운영 비용 ≥ 0 이라는 조건입니다.
- 키워드 3: 최대 집의 수
- 최적의 이익이 아니라, 적자를 보지 않는 선에서 서비스 받는 집의 개수를 최대화하는 것이 목적입니다.
3. 설계 및 접근
- 데이터 입력: 집의 위치를 리스트에 따로 저장합니다. 매번 전체 배열을 도는 것보다 집의 좌표만 체크하는 것이 훨씬 빠릅니다.
- 운영 비용 사전 계산: K에 따른 비용 L = K * K + (K-1) * (K-1)을 미리 계산하거나 함수로 만듭니다.
- 3중 루프 설계:
- 외부: 지도의 모든 좌표 (i, j)를 순회 (중심점 설정).
- 중간: K 값을 1부터 N+1까지 증가 (영역 확장).
- 내부: 저장된 집의 목록을 순회하며 중심점과의 거리가 K-1 이하인지 확인.
- 조건 판별: (집의 개수 × 지불 비용) - 운영비용 ≥ 0 이라면 최대값 업데이트.
4. 예시 시뮬레이션
- 상황: N = 5, K =2, 중심이 (2,2)이고 K = 2
- 운영 비용: 2 *2 + 1 * 1 = 5
- 범위: 맨해튼 거리: $\left\lvert r1 - r2 \right\rvert$ + $\left\lvert c1 - c2 \right\rvert$ < k인 영역.
- 대상 좌표: (1,2), (2,1), (2,2), (2,3), (3,2)
- 집 체크: 집이 (2,2)와 (1,2)에 있다면 총 2가구.
- 수익 계산: (2가구 * 지불 비용 M) - 5
- 결과: 이 값이 0 이상이면 결과값 업데이트
5. 주의 사항
- 실수 포인트: K의 최대 범위 설정
- K가 N일 때 지도를 다 덮는 것 같지만, 모서리 부분까지 모두 커버하려면 K는 N+1까지 커버해야 할 수도 있습니다.
- 문제에 따라 N+1 또는 N+2까지 넉넉히 돌리는 것이 안전합니다.
6. 코드 풀이
6.1 3중 루프 설계
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int k = 1; k <= N + 1; k++) {
CountHome(r, c, k);
}
}
}
- 외부: 지도의 모든 좌표 (r,c)를 순회합니다. (중심점 설정).
- 중간: K 값을 1부터 N+1까지 증가시킵니다. (영역 확장).
- 내부: 저장된 집의 목록을 순회하며 중심점과의 거리가 K-1 이하인지 확인합니다.
6.1.1 CountHome 함수
static void CountHome(int r, int c, int k) {
int homeCnt = 0;
for (int[] home : homes) {
if (Math.abs(home[0] - r) + Math.abs(home[1] - c) < k)
homeCnt++;
}
if (M * homeCnt >= k * k + (k - 1) * (k - 1))
result = Math.max(result, homeCnt);
} // CountHome 종료
- 집의 목록을 순회하며 중심점과의 거리가 k-1이하인지 판정합니다.
- (집의 개수 × 지불 비용) ≥ 운영비용 이라면 최대값을 갱신합니다.
6. 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Solution {
static int N, M; // 지도의 크기, 지불 비용
static int[][] map; // 지도의 정보
static ArrayList<int[]> homes; // 집의 좌표 리스트
static int result; // 서비스 받는 집들의 개수
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
// tc 수행
for (int tc = 1; tc <= T; tc++) {
// N, M 입력
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 초기화
map = new int[N][N];
homes = new ArrayList<>();
result = 0;
// 지도 정보 입력
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
// 집의 정보 리스트에 삽입
if (map[i][j] == 1)
homes.add(new int[] { i, j });
}
}
// 처리
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int k = 1; k <= N + 1; k++) {
CountHome(r, c, k);
}
}
}
// 출력 내용 추가
sb.append("#" + tc + " " + result + "\n");
} // tc 종료
// 출력
System.out.println(sb);
} // 메인 종료
static void CountHome(int r, int c, int k) {
int homeCnt = 0;
for (int[] home : homes) {
if (Math.abs(home[0] - r) + Math.abs(home[1] - c) < k)
homeCnt++;
}
if (M * homeCnt >= k * k + (k - 1) * (k - 1))
result = Math.max(result, homeCnt);
} // CountHome 종료
}