[문제해결을 위한 창의적 알고리즘] 영역 구분 (고급 p.51)
이 문제는 주어진 영역을 반으로 나누어 가며 그 영역이 하얀색으로 다 채워졌는지 혹은 회색으로 다 채워졌는지 확인하는 문제이다. 해결 방법은 주어진 영역을 반으로 나눠가며, 시작 지점과 끝나는 지점 (혹은 정사각형 영역 크기)가 하나의 색으로 다 채워졌는지 확인하고 그렇지 않다면 다시 4등분하여 다시 하나의 색으로 채워졌는지 확인해 나가는 것이다.
코드에서 유의할 만한 사항은 다음과 같다.
1) 2의 배수의 배열 크기를 지정할 때 << bitwise operator를 사용할 수 있다.
2) 흰색의 개수를 세어보고 다시 회색의 개수를 세어보도록 되어 있다.
import java.util.Scanner;
public class DivideAreaSol57 {
// 데이터를 받기 위한 2차원 배열
public static int[][] P = new int[1<<7][1<<7];
public static int n;
// 하나의 색으로 다 채워졌는지 확인
public static boolean isOne(int a, int b, int s, int v) {
for (int i = a; i < a+s; i++)
for (int j = b; j < b+s; j++)
if (P[i][j]!=v)
return false;
return true;
}
// 주어진 영역이 하나의 색으로 다 채워지지 않았다면 길이를 반으로 나눠 재귀 호출
public static int f(int a, int b, int s, int v) {
if (s==1)
return P[a][b]==v?1:0;
if (isOne(a, b, s, v))
return 1;
return f(a,b,s/2,v)
+f(a+s/2,b,s/2,v)
+f(a,b+s/2,s/2,v)
+f(a+s/2,b+s/2,s/2,v);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
P[i][j]=sc.nextInt();
sc.close();
System.out.println(f(0,0,n,0));
System.out.println(f(0,0,n,1));
return;
}
}
Big O(n^2) : n은 주어진 영역의 한변 길이 (모든 값을 다 확인해 봐야 함)
https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/DivideAreaSol57.java
출처: 한국정보올림피아드(2001 전국본선 중등부)