[백준 1030] 프렉탈 평면 (C++)

이 문제는 평범한 재귀와 분할 정복으로 풀어볼려고 했지만 열심히 풀어본 결과 단순히 반복문으로도 풀리는 경우의 문제였다. 물론 재귀적 사고와 분할 정복의 개념을 반복문으로 풀어 쓴 것이다. 반복문으로도 충분히 재귀와 같은 효과를 낼 수 있다.

 

 

전반적인 풀이는 범위 R1, R2, C1, C2에 대해서 각 픽셀당 검정색 칸인가 판별하는 알고리즘이다.

 

 

첫 번째, 제일 중요하게 생각한 것은 큰 문제부터 시작하여 작은 문제로 푸는 것이다.

본문의 예시에서는 s=1 일 때 부터의 예시를 들어서 설명하고 있지만 재귀와 분할정복을 활용하기 위해서는 큰 문제로 부터 시작하여 작은 문제로 줄여가면서 판단해야 한다. 또한 이 문제는 단순히 재귀를 활용하면 경우의 수가 실행시간을 넘어서기 때문에 분할 정복 기법도 사용하여야 한다.

 

두 번째로 집중해서 생각한 것은 검정색 칸의 범위이다.

이 문제는 가로 세로가 같은 정사각형 모양이니 편하게 가로, 세로 중 하나에 집중해서 생각했다. 일정한 '비율'을 가지고 검정색 칸이 커지기 때문이다. 문제를 보면 검정색의 길이는 ( 현재 변의 길이 ) * ( K / N ) 로 줄어든 다는 것을 알 수 있다.

아래의 그림으로 더 자세히 이해해보자.

문제 예시

N=3, K=1, s=2 일 때의 예시 그림을 보여주고 있다. 즉 하얀색 블럭이 3칸이고 검정색 블럭이 1칸이었을 때, s=2이 된다면 이런 그림이 된다는 것이다. 이 구조를 보면 어떠한 패턴으로 그림이 확장되는지 볼 수 있다. 위의 그림은 두 개로 분리하여 생각할 수 있는데 아래 그림과 같다.

s=2 일때, s=2 모양 안에 s=1 모양이 있다

왼쪽의 큰 사각형에 오른쪽 사각형이 8개가 들어가 있는 것을 볼 수 있다. 이것을 보면 큰 사각형이든 작은 사각형이든 이 문제의 검정색 부분은 일정한 비율을 가지고 있는 것을 알 수 있다. 즉, 맨 처음에 말했듯이 ( 현재 변의 길이 ) * ( K / N ) 으로 나타낼 수 있다.

 

세 번째로 집중해서 생각한 것은 s가 줄어들 때 좌표의 변동이다.

우리는 큰 문제에서 작은 문제로 가는 것을 생각해야 하기 때문에, 어떠한 x,y 좌표가 주어졌을 떄 s가 줄어듦에 따라 x,y가 어떻게 변화하는지에 대해 생각을 해야한다. 두 번째에서 설명했듯이 검은색 칸(K)과 같이 전체 크기(N)도 일정하게 줄어드는 것을 생각해 낼 수 있다.

R1, R2, C1, C2 범위 중 위 빨간색 점이 검정인지 판단한다고 생각해보자. s=2일 때, 해당 점은 검정색이 아니니 우리는 s=1로 문제를 분할하여 생각해야 한다. 그럼 빨간색 점의 x,y를 그대로 매개변수로 넘겨서 재귀를 시켜야 하는가? 라고 생각하기엔 여러모로 복잡하게 풀려야 할 것이다. 하지만 s=2에서 그림을 보자면 중앙의 3x3 검은색 칸 주위로 3x3짜리 s=1일 때의 블럭들이 있는 것이 보인다. 즉, 좌표를 축소시켜 하위레벨로 해당 좌표를 넘겨야 한다.

그렇기에 위의 그림과 같이 우리는 해당 x,y 값을 s=1으로 재귀호출 할 때, 각각의 작은 블럭들의 왼쪽 맨위가 x=0, y=0이 되는 절대좌표로 매개변수 값으로 넘겨야 한다. 해당 좌표를 구하는 방법은 s-1의 변의 길이를 구한다음 현재 좌표에 '나머지 연산'을 하면 구해진다. s-1일 때의 x,y의 좌표는 ( x or y ) % { ( 현재 변의 길이 ) / n } 이다.

하위 레벨로 갈 때, x,y 좌표의 축소

 

 

 

전체 알고리즘을 간단히 설명하자면,

반복 : s = 0이 될 때까지

1. 현재 프렉탈 모형의 변 길이를 구한다.

2. 현재 프렉탈 모형의 검정색 부분 변 길이를 구한다.

3. 2번의 길이를 통해 검정색의 시작 좌표와 끝 좌표를 구한다.

4. 현재 s에서 좌표 x,y가 검정색인지 판단한다.

5. x,y 좌표를 축소 시킨다.

6. s = s-1

#include "bits/stdc++.h"

using namespace std;

bool func(int y, int x, int s, int n, int k)
{
    while (s > 0)
    {
        int whiteLength = pow(n, s);                      // 현재 스케일의 전체 크기
        int blackLength = whiteLength / n * k;            // 현재 스케일의 검은색 부분 크기
        int blackStart = (whiteLength - blackLength) / 2; // 검은색 시작 좌표
        int blackEnd = blackStart + blackLength;          // 검은색 끝 좌표

        // 현재 레벨의 검은색 영역에 포함되는지 체크
        if (y >= blackStart && y < blackEnd && x >= blackStart && x < blackEnd)
        {
            return true;
        }

        // 좌표를 축소시켜 하위 레벨로 이동
        y %= whiteLength / n;
        x %= whiteLength / n;

        s--;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int s, n, k, r1, r2, c1, c2;
    cin >> s >> n >> k >> r1 >> r2 >> c1 >> c2;

    for (int i = r1; i <= r2; i++)
    {
        for (int j = c1; j <= c2; j++)
        {
            if (func(i, j, s, n, k))
            {
                cout << "1";
            }
            else
            {
                cout << "0";
            }
        }
        cout << "\n";
    }

    return 0;
}