[BOJ] 1030 프랙탈 평면

문제 링크

 

www.acmicpc.net/problem/1030

 

모든 알고리즘 문제는 C++로 구현되어 있습니다.

 

이 문제는 재귀를 이용한 분할정복으로 해결할 수 있다. 주어진 n과 s를 이용하여 미리 전체 평면의 한 변의 길이를 구해두고, 이중 for문을 이용하여 행 [r1, r2], 열 [c1, c2] 범위의 점들을 하나씩 판정하여 출력해준다. 

 

	int len = 1;
	while (s--) len *= n;
	for (i = r1; i <= r2; i++) {
		for (j = c1; j <= c2; j++) {
			cout << func(len, i, j);
		}
		cout << endl;
	}

 

 

 len에는 전체 평면의 가로 길이가 저장되어 있으며, func 함수는 아래와 같이 작성할 수 있다.

 

int func(int len, int x, int y) {
	if (len == 1) return 0;
	int border = len / n;
	if (x >= border * (n - k) / 2 && x < border * (n + k) / 2 
    && y >= border * (n - k) / 2 && y < border * (n + k) / 2) {
		return 1;
	}
	return func(border, x % border, y % border);
}

 

어떤 점이 한 변의 길이가 l인 평면의 가운데 k*k 영역에 속해있을 경우 이 점은 검정색으로 칠해져 있는 것이며, 이를 판정하기 위해서는 border = l/n이라 했을 때 이 점의 x 좌표와 y좌표가 [border * (n-k) / 2, border * (n-k)/2 + k) 범위 안에 들어있는지를 확인하면 된다. 이 범위 안에 들어있지 않는 경우 func(border, i%border, i%border)를 호출하여 재귀적으로 부분 정사각형에서 이 점이 k*k 범위 안에 들어있는지를 확인한다. l = 1이 되었을 때 0을 리턴한다.

 

전체 코드는 아래와 같다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int s, n, k, r1, r2, c1, c2;

int func(int len, int x, int y) {
	if (len == 1) return 0;
	int border = len / n;
	if (x >= border * (n - k) / 2 && x < border * (n + k) / 2 
    && y >= border * (n - k) / 2 && y < border * (n + k) / 2) {
		return 1;
	}
	return func(border, x % border, y % border);
}

int main() {
	int i, j;
	cin >> s >> n >> k >> r1 >> r2 >> c1 >> c2;
	if (s == 0) {
		cout << 0;
		return 0;
	}
	
	int len = 1;
	while (s--) len *= n;
	for (i = r1; i <= r2; i++) {
		for (j = c1; j <= c2; j++) {
			cout << func(len, i, j);
		}
		cout << endl;
	}
}