[Java] swea 2117 홈방범서비스

[Java] swea 2117 홈방범서비스

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 모의SW_2117_홈방범서비스 {
	static int N, M, MAX;
	static int[][] map;
	static List<int[]> houses;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int testcase = 1; testcase <= T; testcase++) {
			MAX = 0;
			houses = new ArrayList<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			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) houses.add(new int[] {i, j});
				} 
			}
			
			int K;
			if(N % 2 == 0) K = N+1;
			else K = N;
			
			for (int k = K; k >= 1; k--) {
				if(MAX >= (k*k+(k-1)*(k-1))) break;
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						solve(i, j, k);
					}
				}
			} 
			
			System.out.println("#" + testcase + " " + MAX);
		} // tc
	} // main

	private static void solve(int x, int y, int K) {
		int houseCnt = 0;
		for(int[] house : houses) {
			int distance = Math.abs(x-house[0]) + Math.abs(y-house[1]);
			if(distance <= K-1) houseCnt++;
		}
		
		if(houseCnt * M - (K*K+(K-1)*(K-1)) >= 0) {
			if(MAX < houseCnt) MAX = houseCnt;
		}
	} //solve
}

 

K에 따른 서비스 범위 안에 집이 있는 지 체크가 관건..? 인 듯

서비스범위 중심 지점에서 모든 서비스 범위는 K-1 내이다.

 

그러니까 만약 K가 4일 때 중심지점에서 거리가 3인 지점은 모두 서비스 범위!

 

그리고 N이 짝수일 때는 grid를 다 덮을 서비스 범위가 나오려면 K에 +1 해줘야된다.

 

또한 집을 미리 list에 넣어서 solve()함수에선 단지 map 전체를 돌 필요없이 list만 순회했다.

그런데 지금 보니 map을 선언해놨었네...? 

 

어쨌든

 

그래서 그냥 K부터 1까지 줄이면서 , 중심을 (0,0) 에서 (N-1,N-1)까지 쭉 옮기면서 서비스 범위내에 집이 가장 많으면서 손해 보지 않는 경우를 찾으면 된다. 손해보지 않는다고 했으니 이익이 0인 경우도 포함해줬다.

 

끝~!