[문제해결을 위한 창의적 알고리즘] 영역 구분 (고급 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 전국본선 중등부)

문제해결을 위한 창의적 알고리즘 목록