[SWEA JAVA] 2117. [모의 SW 역량테스트] 홈 방범 서비스

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	public static int T, N, M, ans = 0, cnt = 0;
	public static int[][] map;
	public static int[] dr = { -1, 0, 1, 0 };
	public static int[] dc = { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			// 1. 입력받기
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			ans = 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());
				}
			}

			// 2. 방범 서비스를 받을 맵 중심의 좌표
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					cnt = 0;
					homeprotect(i, j, 21);
					if (cnt > ans) {
						ans = cnt;
					}
				}
			}

			// 4. 출력하기
			System.out.println("#" + tc + " " + ans);
		}
	}

	public static void homeprotect(int i, int j, int k) {
		if (k < 1) {
			return;
		}

		int ksize = (k * k) + ((k - 1) * (k - 1)); // 서비스 영역의 크기

		int hsize = bfs(i, j, k); // 해당영역에 집이 몇개 있는지 검사

		if (ksize <= hsize * M) {
			cnt = hsize;
			return;
		} else {
			if (hsize < ans)
				return;
			homeprotect(i, j, k - 1);
		}
	}

	public static int bfs(int i, int j, int k) {
		int sum = 0;
		int[][] visited = new int[N][N];
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] { i, j, 0 });
		visited[i][j] = 1;
		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int r = cur[0];
			int c = cur[1];
			int depth = cur[2];

			if (map[r][c] == 1)
				sum += 1;

			if (depth == k-1)
				continue;

			for (int d = 0; d < 4; d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];

				if (nr < 0 || nr >= N || nc < 0 || nc >= N)
					continue;
				if (visited[nr][nc] == 0) {
					visited[nr][nc] = 1;
					
					q.offer(new int[] { nr, nc, depth + 1 });
				}
			}
		}

		return sum;
	}
}