백준 1030번 프렉탈 평면 - C++(cpp) 풀이

---

 

1. fill(sz, sr, sc) = 원래 보드에서 (sr, sc)를 왼쪽 꼭짓점으로 하고 크기가 sz x sz인 부분 채우기
2. 현재 보드를 N*N개 조각으로 나눴을 때 가운데 K*K조각이 되는 부분을 검은색으로 칠해준다.
3. N*N개 조각으로 나눈 뒤, fill을 재귀적으로 호출해 나머지 부분의 색칠을 완료한다.

 

1. fill(sz, sr, sc) = 원래 보드에서 (sr, sc)를 왼쪽 꼭짓점으로 하고 크기가 sz x sz인 부분 채우기

 프렉탈 무늬가 재귀적으로 생성되므로 분할정복을 이용할 수 있다. fill(sz, sr, sc)를 다음과 같이 정의하자.

 

2. 현재 보드를 N*N개 조각으로 나눴을 때 가운데 K*K조각이 되는 부분을 검은색으로 칠해준다.

 fill에서는 현재 보드를 N*N개 조각으로 나눴을 때 가운데 K*K조각이 되는 부분을 검은색으로 칠해준다. 원래 보드에서의 위치(sr, sc)를 알고 있으므로, 원래 보드의 위치로 평행 이동시켰을 때 (R1, C1)~(R2, C2) 범위에 들어오는 부분을 결과 행렬에 기록해주면 된다.

 

3. N*N개 조각으로 나눈 뒤, fill을 재귀적으로 호출해 나머지 부분의 색칠을 완료한다.

 나머지 더 작은 검은색 조각들은 더 작은사이즈에서 색칠해주면 된다. 크기가 sz/N인 조각 N*N개로 자른 뒤, 각각에 대해 fill을 호출하여 남은 부분의 색칠을 완성한다. 기저 사례는 sz = 1일 때이며, 이때는 흰색으로 그냥 두면 되므로 바로 return 해준다.

반응형

---

#include <iostream>
#include <cmath>

using namespace std;

int S, N, K, R1, R2, C1, C2;
bool res[51][51];

// 원래 보드에서 (sr, sc)를 왼쪽 꼭짓점으로하고 크기가 sz x sz인 부분 채우기
void fill(int sz, int sr, int sc) {
    if (sz == 1) return;
    if (sr > R2 || sc > C2 || sr+sz-1 < R1 || sc+sz-1 < C1) return;
    
    // 가운데 K조각을 검정색으로 채우기
    int black_s = sz/N * (N-K)/2;
    int black_e = black_s + sz/N*K - 1;
    // (R1, C1)~(R2, C2) 범위에 있는 칸만 처리해주면 된다
    int black_r1 = max(R1, black_s+sr);
    int black_c1 = max(C1, black_s+sc);
    int black_r2 = min(R2, black_e+sr);
    int black_c2 = min(C2, black_e+sc);
    for (int i=black_r1; i<=black_r2; i++) {
        for (int j=black_c1; j<=black_c2; j++) {
            res[i-R1][j-C1] = true;
        }
    }
    
    // 남은 부분 재귀적으로 색칠
    for (int i=0; i<sz; i+=sz/N) {
        for (int j=0; j<sz; j+=sz/N) {
            // 검은색으로 이미 칠한 부분 스킵
            if (i >= black_s && i <= black_s && j >= black_s && j <= black_e) continue;
            fill(sz/N, sr+i, sc+j);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> S >> N >> K >> R1 >> R2 >> C1 >> C2;
    
    fill((int)pow(N, S), 0, 0);
    
    for (int i=0; i<R2-R1+1; i++) {
        for (int j=0; j<C2-C1+1; j++) {
            cout << (res[i][j] ? 1 : 0);
        }
        cout << "\n";
    }

    return 0;
}