https://www.acmicpc.net/problem/2630
색종이를 재귀함수를 통해 반복하여 분할정복하는 문제이다.
해당 문제를 풀기 위해 다음과 같은 방법을 설정할 수 있다.
이를 코드를 통해 보면 다음과 같다.
import java.util.*;
public class Main {
static int map[][];
static int[] res = new int[2];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
map = new int[size][size];
for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) map[i][j] = sc.nextInt();
cut(0, 0, size);
System.out.println(res[0]);
System.out.println(res[1]);
}
private static void cut(int sR, int sC, int size) {
if (size == 0) return;
int check = map[sR][sC];
boolean isTrue = true;
CHECK:
for (int i = sR; i < sR + size; i++)
for (int j = sC; j < sC + size; j++)
if(map[i][j] != check) {
isTrue = false;
break CHECK;
}
size /= 2;
if(!isTrue) {
cut(sR, sC, size);
cut(sR, sC + size, size);
cut(sR + size, sC, size);
cut(sR + size, sC + size, size);
}
else res[check] += 1;
return;
}
}