2117 홈 방범 서비스

 

접근

 

1. K값에 따라 영역이 퍼져나가는 특성이 있으므로 BFS를 통해 해당영역의 home이 몇개인지 count하는 방식으로 문제를 해결함.

 

2. K값의 범위에 대해 고민이 있었다. 처음에 K==N 까지만 탐색하면 모든 맵을 체크할 수 있을거라 지레 짐작 했으나, 마지막 TC에서 하나가 모자란 것을 보고 다시 생각하게 되었다. 2*N과 같이 충분히 크게해서 검사해도 괜찮으나 더 나은 성능을 위해 적당한 값으로 설정했다.

 

3. 다른 사람의 코드를 살펴보니, 미리 저장된 home의 좌표를 활용하여 검사하는 지점으로 부터의 거리 k-1 만큼 떨어지 확인하는 Solution이 있었다. 로직이 단순하고 루프가 적다보니, 확실히 속도 측면에서의 이득이 크다.

 

 

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

class Solution {

	static int N, M;
	static int[][] map;
	private static boolean DBG = false;

	static int max;
	static int maxIncome;
	static boolean[][] visited;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// File file = new
		// File("C:\\Users\\Lee\\eclipse-workspace\\TestApplication\\output.txt");
		// PrintStream ps = new PrintStream(new FileOutputStream(file));
		// System.setOut(ps);

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		long startTime = System.currentTimeMillis();
		for (int test_case = 1; test_case <= T; test_case++) {
			max = Integer.MIN_VALUE;
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			map = new int[N][N];
			maxIncome = 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)
						maxIncome += M;
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					// K는 임의로 잡았음(범위조절 필요)
					for (int k = 1; k <= N + 3; k++) {

						// 모든 자원보다 k로 인한 비용이 더 큰 경우는 세지 않는다.
						int cost = k * k + (k - 1) * (k - 1);
						if (maxIncome < cost)
							break;

						visited = new boolean[N][N];
						homeCount = 0;
						bfs(i, j, k);

						if (DBG)
							System.out.printf("i,j[%d %d]k : %d cost : %d income :%d homeCount:%d  maxIncome : %d\n", i,
									j, k, cost, homeCount * M, homeCount, maxIncome);
						if (cost <= M * homeCount) {
							max = Math.max(max, homeCount);
						}

					}
				}

			}

			System.out.println("#" + test_case + " " + max);

		}

		System.out.println(sb);

		if (DBG) {
			long duration = System.currentTimeMillis() - startTime;
			System.out.println("duration : " + duration + "ms");
		}

	}

	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };
	static int homeCount;

	private static void bfs(int sr, int sc, int K) {
		Queue<int[]> Q = new LinkedList<>();
		StringBuilder sb = new StringBuilder();
		Q.offer(new int[] { sr, sc });
		int level = 0;
		while (!Q.isEmpty()) {

			int size = Q.size();
			if (level == K) {
				if (DBG)
					System.out.println("K (level) is " + level);
				return;
			}
			for (int q = 0; q < size; q++) {
				int[] now = Q.poll();
				int r = now[0];
				int c = now[1];

				if (visited[r][c])
					continue;
				visited[r][c] = true;

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

				for (int i = 0; i < 4; i++) {
					int nr = r + dx[i];
					int nc = c + dy[i];
					if (nr >= 0 && nr < N && nc >= 0 && nc < N && !visited[nr][nc]) {
						Q.offer(new int[] { nr, nc });
					}
				}

			}
			++level;
		}

	}

}

 

참고 코드.

    static int security(int r, int c, int k) {
        int count = 0;
        for(int i=0; i<house.size(); i++) {
            House h = house.get(i);
            if(Math.abs(h.row-r) + Math.abs(h.col - c) <= k-1) count++;
        }
        return count;
    }