접근
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;
}
'PS > BOJ' 카테고리의 다른 글
2383 점심 식사시간 (0) | 2022.05.15 |
---|---|
2382 미생물 격리 (0) | 2022.05.14 |
2112 보호필름 (0) | 2022.05.14 |
2105 디저트 카페 (0) | 2022.05.14 |
1953 탈주범 검거 (0) | 2022.05.13 |