|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
class Solution {
private static int zeroCnt = 0, oneCnt = 0;
public static void search(int[][] arr, int rStart, int rEnd, int cStart, int cEnd, int n) {
int cnt = 0;
// 탐색 범위가 1일 때
if (n == 1) {
if (arr[rStart][cStart] == 1)
oneCnt++;
else
zeroCnt++;
return;
}
// 탐색 범위 숫자가 똑같은지 확인
for (int i = rStart; i < rEnd; i++) {
for (int j = cStart; j < cEnd; j++) {
if (arr[i][j] == 1)
cnt++;
}
}
if (cnt == 0) {
zeroCnt++;
} else if (cnt == Math.pow(n, 2)) {
oneCnt++;
} else {
search(arr, rStart, (rStart + rEnd) / 2, cStart, (cStart + cEnd) / 2, n / 2); // 왼쪽 위
search(arr, rStart, (rStart + rEnd) / 2, (cStart + cEnd) / 2, cEnd, n / 2); // 오른쪽 위
search(arr, (rStart + rEnd) / 2, rEnd, cStart, (cStart + cEnd) / 2, n / 2); // 왼쪽 아래
search(arr, (rStart + rEnd) / 2, rEnd, (cStart + cEnd) / 2, cEnd, n / 2); // 오른쪽 아래
}
}
public int[] solution(int[][] arr) {
int[] answer = new int[2];
int n = arr.length;
search(arr, 0, n, 0, n, n);
answer[0] = zeroCnt;
answer[1] = oneCnt;
return answer;
}
}
|
cs |
배열의 범위를 4등분해서 재귀함수로 탐색하였다.