(Java/자바) - SWEA 2117번 : 홈 방범

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

SW Expert Academy

---

• 문제 : 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

 

 

 

---

• 풀이 :

완전탐색으로 해결한 문제였습니다.

 

풀이입니다.

 

1. 모든 좌표,( 0 ~ N)에 대해 k=1부터 N+1까지 범위를 늘려가며 확인한다.

 

2. 이 때, 해당 범위에 있는 집의 개수와 기업이 이득을 보는지 손해를 보는지 확인한다.

 

3. 만약, 현재까지 탐색한 집의 개수 중 MAX값보다 현재 탐색한 집의 개수가 많다면 정답을 갱신한다.

 

 

 

---

• 소스코드 : 

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 TC, N, M, answer, hCount;
	static int[] price;
	static ArrayList<int[]> house;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		TC = Integer.parseInt(br.readLine());
		price = new int[22];
		for (int i = 0; i < 22; i++) {
			price[i] = i * i + (i-1) * (i-1);
		}
		for (int testCase = 1; testCase <= TC; testCase++) {
			sb.append("#").append(testCase).append(" ");
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			answer = 0;
			house = new ArrayList<int[]>();
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					if (st.nextToken().equals("1"))house.add(new int[] {i,j}); 
				}
			}
			for (int k = 1; k <= N+1; k++) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						hCount = 0;
						for (int[] h : house) {
							if(distance(h, i, j) < k) {
								hCount ++;
							}
						}
						if (hCount > answer && hCount*M- price[k] >= 0) {
							answer = hCount;
						}
					}
				}				
			}
			sb.append(answer).append("\n");
		}
		System.out.println(sb.toString());
	}

	private static int distance(int[] h, int i, int j) {
		return Math.abs(h[0] - i) + Math.abs(h[1] - j);
	}
}