[java] sw expert academy - 홈 방범 서비스

문제

SWEA - 홈 방범 서비스
마름모 모양의 방범서비스를 제공할 때 이익을 얻을 수 있는 위치 내 최대 집의 개수를 구하는 문제

풀이

마름모 모양을 어떻게 만드는지가 이 문제의 관건이라고 생각한다

for문 사용

나는 x, y가 마름모의 중심 좌표라고 할 때 2중 for문으로 마름모 영역을 구했다
간만에 펜잡고 계산하며 식을 세웠다..

x, y : 마름모의 중심 위치
k : 마름모의 크기

• 소스코드(영역구하는 2중 for문)

  for (int i = x - k + 1; i < k + x; i++) {
        for (int j = y - (k - 1 - Math.abs(x - i)); j < y + 1 + (k - 1 - Math.abs(x - i)); j++) {
            if (isBoundary(i, j) && map[i][j]) {
                val++;
            }
        }
    }
  

나는 수포자여서 이런 식을 계산하는 데엔 취약하다..

bfs 사용

다르게 생각하면 중심위치부터 인접한 4방향으로 한칸씩 확장한다
확장한 곳에서 또 4방향 확장한다 … 변수를 하나 둬서 k단계까지 확장한다고 생각하고
size만큼 bfs를 돌아도 같은 영역을 확인할 수 있다

고려해야 할 점은
맵의 크기가 10*10 이라고 할 때 전체 집이 포함되게 마름모를 그린다면??

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int N;
	private static int M;
	private static boolean[][] map;
	static int max = Integer.MIN_VALUE;
	static int cost;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < TC + 1; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new boolean[N][N];
			max = 1;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = st.nextToken().equals("1") ? true : false;
				}
			}

			for (int k = 2; k < N + 3; k++) {
				cost = k * k + (k - 1) * (k - 1);
				for (int i = k / 2 - 1; i < N - k / 2+2; i++) {
					for (int j = k / 2 - 1; j < N - k / 2+2; j++) {
						chkCost(i, j, k);
					}
				}
			}
			System.out.println("#" + tc + " " + max);
		}
	}

	private static void chkCost(int x, int y, int k) {
		int val = 0;
		for (int i = x - k + 1; i < k + x; i++) {
			for (int j = y - (k - 1 - Math.abs(x - i)); j < y + 1 + (k - 1 - Math.abs(x - i)); j++) {
				if (isBoundary(i, j) && map[i][j])
					val++;
			}
		}
		if (val * M - cost >= 0)
			max = Math.max(max, val);

	}

	private static boolean isBoundary(int i, int j) {
		if (i > -1 && j > -1 && i < N && j < N)
			return true;
		return false;
	}
}